2
$\begingroup$

I am looking at the proof of the Cook-Levin theorem in Computers and Intractability: A Guide to the Theory of NP-Completeness. In particular, I find one thing unclear. He constructs the statement that is satisfied if and only if transition from step $i$ to step $i+1$ is correct. It goes as follows:

So essentially these statements say that when we are in state $q_k$ at time $i$ and the head is on the square $j$ and reads from it symbol $s_l$, then in the time $i+1$ our head will be at the square $j+\Delta$, we will be in state $k'$ and we will write $s_{l'}$ to the previous square. But I am worried since at no point we check what happens to the rest of the squares, namely if for example we had $ID_i$ to be $0000q_0000$ and $ID_{i+1}$ to be $11111q_511$, shouldn't all the conditions above be satisfied, however this isn't a valid transition?

$\endgroup$

1 Answer 1

2
$\begingroup$

This part is guaranteed by the first subgroup of $G_6$, described in the page 42:

The first subgroup guarantees 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 clauses in this subgroup are as follows: $$\{\overline{S[i, j, l]}, H[i, j], S[i+1, j, l]\}, 0\leqslant i<p(n), -p(n)\leqslant j\leqslant p(n) +1, 0\leqslant l\leqslant v$$

The group $G_6$ is made of the subgroup you quoted and the subgroup above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.