Question

In the proof of the Cook–Levin theorem, a window is a $\mathbf{2}\mathbf{\times }\mathbf{3}$rectangle of cells. Show why the proof would have failed if we had used role="math" localid="1664195743361" $\mathbf{2}\mathbf{\times }\mathbf{2}$windows instead.

Short answer

It has been shown why the proof would have failed if the$2\times 2$ window is used.

Step-by-step solution

Step-1: Cook Levin Theorem

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.

Step-2: Explanation

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\times 2$windows are lawful.

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

a	Q1	b
Q2	a	c

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

0	Q1
Q2	0

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

role="math" localid="1664195737315" $\delta (q1,1)\to (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.

Q1	0
0	Q3

which may or may not be a valid transition. As an example, the outcome of role="math" localid="1664195718976" $\delta (q1,0)\to (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\times 2$ window is used.