- #1
gnome
- 1,041
- 1
OK, that was just to get your attention. I'm not really challenging the NP-completeness of SAT.
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 square j at time i, then the symbol in square j does not change between times i and i+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 square j can change from time i to time i+1 only if the read-write head was looking at tape square j at time i.
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 time i the read-write head is not scanning square j, and also at time i the symbol in square j is not [itex]s_l[/itex], but at time i+1 square j does contain 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?
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 square j at time i, then the symbol in square j does not change between times i and i+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 square j can change from time i to time i+1 only if the read-write head was looking at tape square j at time i.
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 time i the read-write head is not scanning square j, and also at time i the symbol in square j is not [itex]s_l[/itex], but at time i+1 square j does contain 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?