C
[email protected]
- Jan 1, 1970
- 0
A few days ago, I read the following paper www.cs.auckland.ac.nz/~cristian/SAT_Paper.pdf
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
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