C

#### [email protected]

- Jan 1, 1970

- 0

This led me to think that perhaps there is a way to solve the Boolean

Satisfiability problem (SAT) using electronic circuits in the most

simple but fastest possible way imaginable, which to me seems almost

too good to be true, since it would solve SAT in constant time,

assuming that my knowledge of electronic circuits is correct:

Let's suppose that we want to determine just like the example in the

above paper whether the circuit (a + b)*(a' + b) is satisfiable, where

a' is (NOT a). (+ means OR and * means AND.)

Let's say we have a battery with the cathode (negative terminal) wire

branching into three wires representing the variables a, a', and b,

where a' is just a after going through a NOT gate (using transistors).

Then apply, using transistors, the gates for (a + b)*(a' + b) to the

three branches a, a', and b. Then connect the output wire from these

gates to the anode (positive terminal) of the battery.

Since the formula (a + b)*(a' + b) is logically satisfiable, the

corresponding electronic circuit should yield some positive current

when the circuit is closed. If (a + b)*(a' + b) were not satisfiable

and were instead something like (a + b')*(a' + b)*(a + b)*(a' + b'),

then the current would be zero when we try to close the circuit.

So unless I am missing something, it seems that in order to solve the

NP-complete Boolean satisfiability problem, we just need to set up a

corresponding circuit using common electronic devices.

The conventional wisdom is that hard instances of NP-complete problems

cannot be solved in real time in the real world: See

http://www.arxiv.org/abs/quant-ph/0502072

The scenario that I have described in this post seems to contradict

conventional wisdom. In other words, the general belief in the

computer science community that P != NP might be irrelevant,

practically speaking. We can get around this problem by designing

integrated circuits which solve NP-complete problems in constant time.

Can someone show me where I am wrong? (I am no expert in electronics,

so I am expecting to be wrong.)

Craig Feinstein