91Ó°ÊÓ

The Cook–Levin theorem, often known as Cook's theorem, claims that the Boolean satisfiability problem is -complete in computational complexity theory. That is, it is in , and any problem may be reduced to the Boolean satisfiability problem in polynomial time by a deterministic Turing machine.

When checking the left moves of the head, problems can emerge. It can illustrate, for example, that there are two rows of configuration, with the top row being a valid configuration and the bottom row not being a configuration that could be formed by the transition function from the top row, but all $2×2$windows are lawful.

Take a look at the $2×3$window below, where the top row is part of the legal arrangement (bottom row does not legally follow.)

The $2×2$windows scheme, on the other hand, is unable to detect this issue. It just looks at the two windows below:

Which may or may not be a valid transition. As an example, the outcome of

role="math" localid="1664195737315" $\mathrm{δ}(q1,1)→(q2,1,L)$

The problem is that this window cannot see whether the head is looking at a 1 or a 0 , so it is assumed that it is valid.

which may or may not be a valid transition. As an example, the outcome of role="math" localid="1664195718976" $\mathrm{δ}(q1,0)→(q3,0,R)$.

If both of these tests pass, an issue will arise. Therefore, it has been explainedwhy the proof would have failed if the $2×2$ window is used.