I just need some help with the Cook-Levin theorem (SAT is NP-complete). The proof of this theorem is not so clear to me. I use Sipser's book "Introduction to the Theory of Computation". Up to this proof, everything else seems very clear and obvious; therefore I chose this book. The proof is on the page 277.
I can't understand the concept of the tableau from the very beggining .
In particular,
every row in tablea presents branch with states if corresponding nodes in TM?
what is the idea of window stands for ?
May be there is any simplified version, you know of?
Thanks!
Thanks for great explanation!
I would like to ask you few more questions
the idea of tableau is clear
the idea of cell is clear
but I still have a problem with designing $\phi$ (correspond boolean expression to input $\omega$)
Now we design $\phi$ so that a satisfing assignment to the variables does correspond to an accepting tableau for N on $\omega$. The formula for $\phi$ is the AND of four parts $\phi_{cell}\wedge\phi_{start}\wedge\phi_{move}\wedge\phi_{accept} $ (how can this construction describe $\phi$?) . We describe each part in turn.
As we mentioned previously, tunrning variable $x_{i,j,s}$ on corresponds to placing symbol $s$ in $cell[i,j]$ The first thing we must guarantee in order to obtain a correspondence beetwen an assignment and a tableau is that the assignment turns on exactly one variable for each cell. Formula $\phi_{cell}$ ensures this requirments by expressing it in terms of Boolean operations
$\phi_{cell} = \underset{1\leqslant i, j\leqslant n^{k}}{\wedge }\left [ \left ( \underset {s\epsilon C}{\wedge} x_{x,j,s} \right ) \wedge \left (\underset{\underset{s\neq t}{s,t\epsilon C}}{\wedge} \left ( \overline{x_{i,j,s}} \vee \overline{x_{i,j,t}} \right ) \right ) \right ]$
Why $\phi_{cell}$ has a above equation?
Thanks!