1. The Cook-Levin Theorem

The Cook-Levin Theorem

Cook-Levin Theorem

The Cook-Levin Theorem states that the Boolean Satisfiability Problem (SAT) is NP-complete.

Link to original

Proof

We want to show that every problem $X\in \text{NP}$ can be reduced to SAT.

1. Let $X\in \text{NP}$ be any problem belonging to class NP.
2. By definition of class NP, there must be some NDTM $M$ such that $M$ has a polynomial-length computation that accepts $w$ $⟺$ $w\in X$.
3. For each state $q\in Q$:
   • Where symbol $a\in \Sigma$.
   • Where integers $i,t\le T_M(n)$ (i, t are less than termination time on the input $w$).
   • Let $C_{i,t,a}$ be whether the cell $i$ of the $M$‘s tape contains the symbol $a$ at some given time $t$.
   • Let $H_{i,t}$ be whether the tape head is in position $i$ at a given time $t$.
   • Let $S_{q,t}$ be whether the machine is in state $q$ at a given time $t$.

Example

Using these newly introduced propositional variables, we can argue things such as:

• $\boxed{\neg (S_{q_4,2}\wedge S_{q_5,2})}$: “The machine cannot be in both state $q_4$ and $q_5$ at the given time $t=2$”
• $\boxed{(H_{0,3},H_{1,3},H_{2,3},H_{3,3})}$: “At the given time $t=3$, the tape head must be in positions $0,1,2,$ or $3$”
• $\boxed{C_{3,1,a}\to \neg C_{3,1,b}}$: “At the given time $t=1$, if cell $1$ contains an $a$ then it must not contain a $b$”
• $\boxed{(S_{q_1,6}\wedge H_{4,6}\wedge C_{4,6,a})\to (S_{q_2,7}\wedge H_{3,7}\wedge C_{4,7,b})}$: “At the given time $t=6$, if the machine is in state $q_1$ and the tape head is in position $4$ and the corresponding cell contains an $a$, then at time $t=7$: the machine will be in state $q_2$, the tape head will move to position $3$ and cell $4$ will now contain a $b$”

4. With these propositional variables, we can construct a formula: $F_M,w=M$ has a polynomial-length computation that accepts $w$.
5. We also have that $w\in X⟺F_{M,w}\text{ is satisfiable}$.
6. Hence it follows that $X{\le }_p\text{SAT}$ for all $X\in \text{NP}$.
7. Since we we already know that SAT belongs to NP, it must follow that SAT is NP-complete.