1. Home
  2. Electronics Design
  3. Naive Question about the Boolean Satisfiability Problem

Naive Question about the Boolean Satisfiability Problem

A few days ago, I read the following paper

formatting link

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

formatting link

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

Reply to
cafeinst
Loading thread data ...

Craig, you have become sort of a celebrity here! Do you know this paper?

formatting link

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.

Reply to
hbdere

snipped-for-privacy@msn.com wrote: ...

...

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.'

formatting link
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

Reply to
Patricia Shanahan

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.

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

Reply to
Craig Feinstein

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

Reply to
Craig Feinstein

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

Patricia

Reply to
Patricia Shanahan

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 Patricia

Reply to
Craig Feinstein

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

Reply to
Craig Feinstein

I need more detail here, or some examples:

how would I model a or 'a or a+b or a+'b

many NP problems can be solved in constant or linear time by exploiting a physical model as complex as the expression of the problem.

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

Reply to
jasen

On 2007-04-05, Craig Feinstein wrote: )

...

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

Reply to
jasen

formatting link

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

Reply to
Jan

paperwww.cs.auckland.ac.nz/~cristian/SAT_Paper.pdf

I don't think my idea will work. I am now also a bit skeptical of the idea in the article

formatting link

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:

formatting link

Craig

Reply to
Craig Feinstein

I can only see this working with a quantum computer

Bye. Jasen

Reply to
jasen

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.