Connect with us

Naive Question about the Boolean Satisfiability Problem

Discussion in 'Electronic Design' started by [email protected], Apr 5, 2007.

Scroll to continue with content
  1. Guest

    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
     
  2. hbdere

    hbdere Guest

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

    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
     
  4. 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
     
  5. 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
     
  6. How would you make that happen, and yet not have current flow for
    unsatisfiable formulas?

    Patricia
     
  7. 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
     
  8. 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
     
  9. jasen

    jasen Guest

    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
     
  10. jasen

    jasen Guest

    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
     
  11. Jan

    Jan Guest

    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?!
    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
     
  12. 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
     
  13. jasen

    jasen Guest

    I can only see this working with a quantum computer


    Bye.
    Jasen
     
Ask a Question
Want to reply to this thread or ask your own question?
You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.
Electronics Point Logo
Continue to site
Quote of the day

-