Maker Pro
Maker Pro

Naive Question about the Boolean Satisfiability Problem

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
 
H

hbdere

Jan 1, 1970
0
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.
Craig, you have become sort of a celebrity here! Do you know this
paper?
http://www.scottaaronson.com/papers/npcomplete.pdf

Maybe you just need to ask yourself why anyone should ever have
doubted that it is easy to build a machine solving one single SAT
instance in constant time? You can even use a computer to do so: solve
the instance by hand somehow, then put it and its result in a lookup
table, use a good hash function, and voila - constant time henceforth
(or linear time for the hash function, whatever)!

Have fun,
H.
 
P

Patricia Shanahan

Jan 1, 1970
0
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.
....

This procedure tests whether a and b both true satisfies the expression.
It does not test whether it is satisfied by any of the other three
combinations. For example, it would reject as unsatisfiable (a + b)*(a'
+ b')

One definition of NP is 'the set of problems whose solutions can be
"verified" by a deterministic Turing machine in polynomial time.'
[http://en.wikipedia.org/wiki/NP_(complexity)], so fast verification of
a possible SAT solution is not surprising.

The problem with the brute force testing of solutions to NP-complete
problems is that the number of possible solutions that need to be tested
increases exponentially with problem size.

You would need to test four different wirings before your procedure
could reject a two variable expression, eight wirings for a three
variable expression, 65,536 wirings for a 16 variable expression...

Patricia
 
C

Craig Feinstein

Jan 1, 1970
0
[email protected] wrote:

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

...

This procedure tests whether a and b both true satisfies the expression.
It does not test whether it is satisfied by any of the other three
combinations. For example, it would reject as unsatisfiable (a + b)*(a'
+ b')

Not true. It would accept (a+b)(a'+b') as satisfiable, as there is
nothing stopping current from flowing through wires a' and b or wires
a and b'. Such a procedure would have to be nondeterministic.
One definition of NP is 'the set of problems whose solutions can be
"verified" by a deterministic Turing machine in polynomial time.'
[http://en.wikipedia.org/wiki/NP_(complexity)], so fast verification of
a possible SAT solution is not surprising.

The problem with the brute force testing of solutions to NP-complete
problems is that the number of possible solutions that need to be tested
increases exponentially with problem size.

You would need to test four different wirings before your procedure
could reject a two variable expression, eight wirings for a three
variable expression, 65,536 wirings for a 16 variable expression...

Not true. Read my description again. You only need to set up one
polynomial-size circuit for this to work. All you have to do is build
a circuit corresponding to the Boolean expression in question. If the
circuit produces some current flow, then the Boolean expression can be
satisfied. If not, then the Boolean expression is identically zero and
cannot be satisfied.

I'm looking for a reason, if one exists, why such a procedure won't
work. If there is no reason why the procedure won't work for any
Boolean expression, then it is possible to build integrated circuits
which solve NP-hard problems efficiently. This would of course
revolutionize computer science.

Or of course, I could be overlooking something, as I am not an expert
in electrical engineering.

Craig
 
C

Craig Feinstein

Jan 1, 1970
0
I'm now very skeptical of this idea. Someone emailed me asking what
happens if the formula is NOT(a)? Does current flow through the
circuit or not? This seems to be a problem. In any case, the paper
that I linked on my first post is quite interesting.

Craig
 
P

Patricia Shanahan

Jan 1, 1970
0
Craig said:
Not true. It would accept (a+b)(a'+b') as satisfiable, as there is
nothing stopping current from flowing through wires a' and b or wires
a and b'. Such a procedure would have to be nondeterministic.

How would you make that happen, and yet not have current flow for
unsatisfiable formulas?

Patricia
 
C

Craig Feinstein

Jan 1, 1970
0
Patricia said:
How would you make that happen, and yet not have current flow for
unsatisfiable formulas?

With great difficulty. I now don't think my idea would work. The best
such a method could do is perhaps solve the fractional version of SAT,
where for each variable x, 0<=x<=1. So I'll say "Never mind". However,
the paper that I linked to at the beginning of the post is a good read
and is thought-provoking. I'm still intrigued by the example given in
this paper in Appendix B.

Craig
 
C

Craig Feinstein

Jan 1, 1970
0
With great difficulty. I now don't think my idea would work. The best
such a method could do is perhaps solve the fractional version of SAT,
where for each variable x, 0<=x<=1. So I'll say "Never mind". However,
the paper that I linked to at the beginning of the post is a good read
and is thought-provoking. I'm still intrigued by the example given in
this paper in Appendix B.

Actually, Appendix B is not in the paper that I linked above. It comes
from Josh Arulanandham's PhD thesis on Natural Algorithms, which I
downloaded a few days ago, but is unfortunately now gone.

Craig
 
J

jasen

Jan 1, 1970
0
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.

I need more detail here, or some examples:

how would I model a or 'a or a+b or a+'b
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

many NP problems can be solved in constant or linear time by exploiting a
physical model as complex as the expression of the problem.
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.)

FWIW ISTM that these problem can be solved in 2^N time (for n variables)
using a FPGA configured to repsent the expression


Bye.
Jasen
 
J

jasen

Jan 1, 1970
0
On 2007-04-05 said:
Not true. It would accept (a+b)(a'+b') as satisfiable, as there is
nothing stopping current from flowing through wires a' and b or wires
a and b'. Such a procedure would have to be nondeterministic.
....
I'm looking for a reason, if one exists, why such a procedure won't
work. If there is no reason why the procedure won't work for any
Boolean expression, then it is possible to build integrated circuits
which solve NP-hard problems efficiently. This would of course
revolutionize computer science.

Or of course, I could be overlooking something, as I am not an expert
in electrical engineering.

Describe this circuit in detail, and how it is derived from the boolean
expression.

(and, if not immedately obvious how this derivation can be done in polynomial time)

Describe also the circuit for (a+b)(a'+b')(a+b')(a'+b)

Bye.
Jasen
 
J

Jan

Jan 1, 1970
0
A few days ago, I read the following paper www.cs.auckland.ac.nz/~cristian/SAT_Paper.pdf

I have only read the article very causally but:
I think they skip the design description for a very crucial point in
their construction - "the perfect seesaw". How will they implement it
without adding additional forces to their model? The fact that the on-
state thresholds for the OR and AND gates are different, doesn't make
that task easier... And will their model always have a stable state?!
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).

Rephrasing Patricia:
You're assigning the variables in this step by wiring them to the same
electrical potential i.e. a=b= ... etc. You're construction look more
like an attempt to implement a Boolean Circuit in hardware - with
equally assigned variables. In the article you've read, the unresolved
variables initially "float".

Regards Jan
 
C

Craig Feinstein

Jan 1, 1970
0
I have only read the article very causally but:
I think they skip the design description for a very crucial point in
their construction - "the perfect seesaw". How will they implement it
without adding additional forces to their model? The fact that the on-
state thresholds for the OR and AND gates are different, doesn't make
that task easier... And will their model always have a stable state?!


Rephrasing Patricia:
You're assigning the variables in this step by wiring them to the same
electrical potential i.e. a=b= ... etc. You're construction look more
like an attempt to implement a Boolean Circuit in hardware - with
equally assigned variables. In the article you've read, the unresolved
variables initially "float".

Regards Jan

I don't think my idea will work. I am now also a bit skeptical of the
idea in the article www.cs.auckland.ac.nz/~cristian/SAT_Paper.pdf

The question I have is how does the machine described in the article
prevent fractional solutions to the SAT problem? It may be possible
that there are fractional solutions (between zero and one) to SAT but
no zero-one solutions.

So maybe there is no way to get around P != NP. I doubt quantum
computing will work practically and I doubt quantum computing can
theoretically solve NP-Hard problems in polynomial time.

Here is a link to Joshua J. Arulanandham's site, which was not there
yesterday: http://www.cs.auckland.ac.nz/~jaru003/

Craig
 
J

jasen

Jan 1, 1970
0
I can only see this working with a quantum computer


Bye.
Jasen
 
Top