Cook - Levin Theorem

Around 1971, Cook and Levin independently discovered the notion of $NP-completeness$ and gave examples of combinatorial $NP-complete$ problems whose definition seems to have nothing to do with Turing machines. Soon after, Karp showed that $NP-completeness$ occurs widely and many problems of practical interest are $NP-complete$. To date, thousands of computational problems in a variety of disciplines have been shown to be $NP-complete$.

$SAT$ is the language of all satisfiable $CNF$ formulae.

Cook-Levin Theorem: $SAT$ is $NP-complete$

Before we go into the proof first we need to define some things

Configuration of a Turing Machine: A configuration of a Turing Machine at any point of time $t$ is basically the snapshot of the turning machine at that time. It is an ordered pair of the head position, current state, and tape content. Any configuration is initialized and ended with a special symbol, let $\#$ mark its ending. Then the contents of the tape at the left of the head, then the current state then the content of the cell where the head is pointed and the content of the tape at the right of the head. So if any configuration is like $(\#, w_1,w_2,q,w_3,w_4,w_5,w_6,\#)$ then the head is pointed at 3rd letter in state $q$ and the content of the tape is $w_1w_2w_3w_4w_5w_6$

Computation Tableau of a Turing Machine: It is a table of configurations where form $i-$the row to $i+1-$the row it follows the turning machine's transition function at time $i$ on any input $x$ and the first row is the starting configuration. A tableau is accepting if any in the tableau is an accepting configuration.

Now let's come to the proof of the theorem.

Proof: Let $L$ be any language in $NP$. Then there exists a nondeterministic turning machine $M$ with runtime $n^k$ and $L=\mathcal{L}(M)$.

Idea: The idea is to encode the computation tableau of $M$ on input $x$, $|x|=n$ to a boolean formula $\varphi$ such that there is an accepting configuration iff $\varphi \in SAT$

Let $x=w_1w_2\dots w_n$. Let $C=Q\cup \Gamma\cup \{\#\}$ where $Q$ is the set of states of $M$ and $\Gamma$ is set of alphabets of $M$. Since the Turing machine runs for time $n^k$ it can at most access $n^k$ space, So the computation tableau will have $n^k$ rows and $n^k$ columns. Now the initial configuration is $$(\#,q_0,w_1,w_2,\dots,w_n,\sqcup,\dots,\sqcup,\#)$$ Now any cell in the tableau contains a symbol from $C$. So for each $(i,j)-$the cell and $s\in C$ introduce a variable $x_{i,j,s}$. $x_{i,j,s}=1$ iff the $(i,j)-$the cell in the tableau has the symbol $s$, otherwise $x_{i,j,s}=0$.

Therefore we can encode the starting configuration as $$\varphi_{start}=x_{1,1,\#}\wedge \left( \bigwedge_{j=2}^{n+1} x_{1,j,w_{j-1}} \right) \wedge \left( \bigwedge_{j=n+2}^{n^k-1} x_{1, j,\sqcup} \right)\wedge x_{1,n^k,\#}$$ Now setting $x_{i,j,s} =1$ corresponds to placing $s$ in $(i,j)-$the cell. To obtain a correspondence between an assignment and a tableau, we must ensure that the assignment sets to 1 exactly one variable for each cell. First, we need to ensure each cell has at least one symbol placed in it. We do it by $\bigvee\limits_{s\in C} x_{i,j,s}$. Now we have to ensure that the cell does not have more than two symbols placed in it. We do it by $\bigvee\limits_{s,t\in C, s\neq t} (\overline{x_{i,j,s}}\wedge\overline{x_{i,j,t}})$. Hence for each cell, these two conditions both should follow, therefore $$\left(\bigvee\limits_{s\in C} x_{i,j,s}\right) \wedge \left( \bigvee\limits_{s,t\in C, s\neq t} (\overline{x_{i,j,s}}\wedge\overline{x_{i,j,t}})\right)$$ There condition should follow for every cell, therefore, we get the second part for our desired boolean function $$\varphi_{cell}=\bigwedge_{1\leq i,j\leq n^k}\left[ \left(\bigvee\limits_{s\in C} x_{i,j,s}\right) \wedge \left( \bigvee\limits_{s,t\in C, s\neq t} (\overline{x_{i,j,s}}\wedge\overline{x_{i,j,t}})\right)\right]$$

Formula $\varphi_{accept}$ guarantees that an accepting configuration occurs in the tableau. The formula ensures that $\varphi_{accept}$, the symbol for the accept state, occurs in one of the cells of the tableau by stipulating that one of the corresponding variables is set to 1. Hence the formula for it is $$\varphi_{accept}=\bigwedge_{1\leq i,j\leq n^k} x_{i,j,q_{accept}}$$

The last part of the formula has to do with the transitions of the Turing machine. Here we use the concept of the window in the computation tableau

$\boldsymbol{(i,j)-6}$ window in a Computation Tableau: A window in the tableau is a $2\times 3$ piece with adjacent rows and columns.

A window is legal if it does not violate the transition function of the turing machine. Determining which windows are legal can be done by case analysis. 

Say $\delta(q_1,a)=(q_1,b,R)$ $\delta(q_1,b)=\{(q_2,c,L),(q_2,a,R)  \}$

Hence $$\varphi_{move}=\bigwedge_{1\leq i,j\leq n^k} ((i,j)-6\text{ window is legal})$$

Therefore the final boolean circuit is $$\varphi=\varphi_{start} \wedge \varphi_{cell} \wedge \varphi_{move} \wedge \varphi_{accept}$$  $\blacksquare$