Notes - Computational Complexity HT25, Cook-Levin theorem

$\mathsf{SAT}$ is $\mathsf{NP}$-complete.

$\mathsf{SAT}$ is $\mathsf{NP}$: A nondeterministic polynomial time machine can guess an assignment to the variables in a formula $\varphi$ and accept if the assignment satisfies $\varphi$.

---

$\mathsf{SAT}$ is $\mathsf{NP}$-hard: Fix some $\mathsf{NP}$ language $A$ with a corresponding NTM

\[N = (Q, \Sigma, \Gamma, \delta, q_0, q_\text{acc}, q_\text{rej})\]

deciding $A$ in polynomial time. We may assume that $N$ runs in time $n^k$ for some constant $k$, and that it uses just a single tape (this is justified by the fact any $\ell$-tape NTM can be simulated by a single tape one).

A tableau for $N$ on input $w$ is an $n^k \times n^k$ table whose rows are the configurations of a particular branch of $N$ on input $w$.

Each row corresponds to the contents of the tape in that configuration, along with the current state and the pointer. The location of the pointer is represented implicitly as being over the cell to the right of the current state symbol (so for example, if the row is $#w _ 1 w _ 2 q _ i w _ 3#$, this represents that the tape’s contents are $w _ 1 w _ 2 w _ 3$ and the pointer is over $w _ 3$).

Say a tableau is accepting if any row of the tableau is an accepting configuration, so that every accepting tableau for $N$ on $w$ corresponds to an accepting computation branch of $N$ on $w$. So the problem of determining whether $N$ accepts $w$ is equivalent to the problem of determining whether an accepting tableau for $N$ on $w$ exists. We formulate this problem as determining the satisfiability of a CNF formula

\[\varphi = \varphi_\text{start} \land \varphi_\text{accept} \land \varphi_\text{cell} \land \varphi_\text{move}\]

Variables of $\varphi$: Let $C = Q \cup \Gamma \cup \{#\}$. The variables of $\varphi$ are $x _ {i, j, s}$ where $1 \le i, j \le n^k$, $s \in C$. Intuitively, we wish

\[x_{i, j, s} = 1 \iff \text{cell }(i, j) \text{ contains }s\]

$\varphi _ \text{start}$ fixes the start of the tableau:

\[\varphi_\text{start} = x_{1, 1, \#} \land x_{1, 2, q_0} \land \cdots \land x_{1, n^k - 1, \sqcup}\land x_{1, n^k, \#}\]

$\varphi _ \text{accept}$ ensures that an accepting configuration occurs:

\[\varphi_\text{accept} = \bigvee_{1 \le i, j \le n^k} x_{i, j, q_\text{acc} }\]

$\varphi _ \text{cell}$ ensures that each cell is filled with exactly one symbol (possibly blank):

\[\varphi_\text{cell} = \bigwedge_{1 \le i, j \le n^k} \left[ \left( \bigvee_{s \in C} x_{i, j, s} \right) \land \left( \bigvee_{s, t \in C, s \ne t} (\overline{x_{i, j, s} } \lor \overline{x_{i, j, t} }) \right) \right]\]

$\varphi _ \text{move}$ guarantees that each row of the configuration legally follows from the previous row: Call a $2 \times 3$ window of cells legal if that window does not violate the actions specified by $N$’s transition function.

\[\varphi_\text{move} = \bigwedge_{1 \le i < n^k, 1 < j < n^k} \varphi_\text{legal}(i, j)\]

where

\[\varphi_{\text{legal}(i, j)} = \bigvee_{a_1, \ldots, a_6 \text{ is legal window}} x_{i, j-1, a_1} \land x_{i, j, a_2} \land x_{i, j+1, a_3} \land x_{i+1, j-1, a_4} \land x_{i+1, j, a_5} \land x_{i+1, j+1, a_6}\]

We claim that if the top row of the tableau is the start configuration and every window in the tableau is legal, each row of the tableau is a configuration that follows from the preceding one.

Consider two adjacent configurations in the tableau, call these the upper configuration and the lower configuration. In the upper configuration, every cell that contains a tape symbol that isn’t adjacent to a state symbol is the centre top cell in a window whose top row contains no states. Therefore, that symbol must appear unchanged in the centre bottom of the window. Hence it appears in the same position in the bottom configuration.

The window containing the state symbol in the centre top cell guarantees that the corresponding three positions are updated consistently with the transition function. Therefore, if the upper configuration is a legal configuration, so is the lower configuration, and the lower one follows the upper one according to $N$’s rules. (@todo, illustration)

---

Note that all these formulas are polynomially sized, and that this formula can be constructed in polynomial time (one slight complication is that we need an extra logarithmic factor to index the variables, but this does not matter since we can consider a larger polynomial).

Hence $\mathsf{SAT}$ is $\mathsf{NP}$-complete.