OK, that was just to get your attention. I'm not really challenging the NP-completeness of SAT.(adsbygoogle = window.adsbygoogle || []).push({});

And maybe I'd be going too far even just claiming to have found a flaw in one of the most widely cited proofs of Cook's Theorem. So let's just assume that I'm wrong, and someone please show me why.

The proof described in chapter 2 of Garey & Johnson, "Computers and Intractibility", involves a reduction of all the languages in NP to SAT by defining an NDTM M, specified by [itex]\Gamma, \Sigma, b, Q , q_0, q_Y, q_N, \text{and}\; \delta[/itex], such that establishing membership of a string x in some language L [itex]\in[/itex] NP is equivalent to finding a satisfying truth assignment to a CNF formula. (OK I'm probably grossly oversimplifying, but you know what I mean.)

To accomplish this, the formula will be built up from 3 types of variables, specifically:

[tex]\begin{array}{ll}\mbox{Variable} &\mbox{Meaning}\\

Q[i,k] &\mbox{At time i, M is in state}\, q_k\\

H[i,j] &\mbox{At time i, the read-write head}\\

&\mbox{ is scanning tape square j}\\

S[i,j,k] &\mbox{At time i, the contents of}\\

&\mbox{tape square j is symbol}\, s_k\end{array}[/tex]

These variables are placed into six groups of clauses with the intended result that a truth assignment on the variables that satisfies the CNF formula will occur if and only if the NDTM M halts in its accepting state in polynomial time. i.e. (formula is satisfied) [itex]\equiv[/itex] (x [itex]\in[/itex] L).

The clause groups are:

[tex]\begin{array}{ll}\mbox{Clause group} \quad &\mbox{restriction imposed}\\

G1 &\mbox{At each time i, M is in exactly one state.}\\

G2 &\mbox{At each time i, the read-write head is scanning}\\

&\mbox{exactly one tape square.}\\

G3 &\mbox{At each time i, each tape square contains}\\

&\mbox{exactly one symbol from}\, \Gamma.\\

G4 &\mbox{At time 0, the computation is in the initial}\\

&\mbox{configuration of its checking stage for input x.}\\

G5 &\mbox{By time p(n), M has entered state} \, q_Y\\

&\mbox{and hence has accepted x.}\\

G6 &\mbox{For each time i,} \, 0 \leq i \leq p(n) \,\mbox{ the configuration}\\

&\mbox{of M at time i+1 follows by a single}\\

&\mbox{application of the transition function} \, \delta\\

&\mbox{from the configuration at time i.}\end{array}[/tex]

Actually, Group 6 is divided into 2 sub-groups. the first sub-group is to guarantee that if the read-write head is not scanning tape squarejat timei, then the symbol in squarejdoes not change between timesiandi+1. The other subgroup of G6 guarantees that the changes from one configuration to the next are in accord with the transition function [itex]\delta[/itex] for M.

Now, to have a valid reduction, it must be so that a machine that correctly recognizes L must correspond to a truth assignment that satisfies all of these clauses. And conversely, there must not be a truth assignment that satisfies all of the clauses but is not a valid, accepting computation of L.However, I don't think that the clauses supplied are sufficient to accomplish this. My problem is with the first subgroup of Group 6. The clauses in that subgroup are of the form:

[tex]\{\overline{S[i,j,l]}, H[i,j], S[i+1,j,l]\}[/tex]

To reiterate, that was supposed to ensure that the contents of tape squarejcan change from timeito timei+1onlyif the read-write head was looking at tape squarejat timei.

Suppose we have this truth assignment for some clause [itex]c_a[/itex]:

[tex]\begin{array}{ll}\text{True} &\overline{S[i,j,l]}\\

\text{False} &H[i,j]\\

\text{True} &S[i+1,j,l]}\end{array}[/tex]

This means that at timeithe read-write head isnotscanning squarej, and also at timeithe symbol in squarejisnot[itex]s_l[/itex], but at timei+1 square jdoescontain symbol [itex]s_l[/itex]. Since the clause is a disjunction, it is true. And therefore the entire formula (a conjunction of these disjunctive clauses) may be satisfied. But clearly this does not represent a valid computation of L, right?

Then the whole proof is out the window, unless someone can come up with some clause or group of clauses (remember they must be disjunctions) that fulfill the mission of the first subgroup of G6. I haven't been able to. Can you?

**Physics Forums - The Fusion of Science and Community**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# SAT is NP-complete (?)

Loading...

Similar Threads - complete | Date |
---|---|

Lattice/Complete lattice | Jun 10, 2014 |

Confidence of complete spatial randomness | May 8, 2014 |

Complete Random Design vs RCBD | Sep 7, 2013 |

Completeness notions in logic | Feb 23, 2013 |

Graph theory - complete subgraphs | Feb 23, 2012 |

**Physics Forums - The Fusion of Science and Community**