Cook's Theorem (1971) — SAT is NP-Complete

Statement:
The Boolean Satisfiability problem (SAT) — given a Boolean formula $\phi$ in CNF, is there an assignment making $\phi$ true? — is NP-complete.

More precisely Cook proved CNF-SAT is NP-complete; Levin independently proved general SAT. Hence 3-SAT is also NP-complete.

Proof Idea

Must show (1) SAT $\in$ NP and (2) SAT is NP-hard: every $L \in$ NP polytime-reduces to SAT.

1. SAT $\in$ NP: certificate = satisfying assignment, verifier checks formula in polytime.

2. Every NP language reduces to SAT:

   • Let $L \in$ NP decided by nondeterministic TM $M$ in time $p(n)$ (polynomial).
   • For input $x$, $|x|=n$, construct Boolean formula $\phi_x$ that encodes the entire computation tableau of $M$ on $x$: variables represent tape cells, head position, state at each time step $t=0..p(n)$.
   • Add clauses enforcing: initial configuration = $x$, each step follows $M$'s transition relation, and final state is accepting.
   • $\phi_x$ is satisfiable iff there exists an accepting computation path of $M$ on $x$.
   • Size of $\phi_x$ is $O(p(n)^2)$ — polynomial.
   • Conversion $x \mapsto \phi_x$ is deterministic polytime.
     Hence $x \in L \iff \phi_x \in$ SAT → $L \le_p$ SAT.

Significance

• First NP-complete problem — seeds all other NP-completeness proofs by reduction from SAT.
• Implies $P = NP \iff$ SAT $\in$ P.
• Foundations of complexity theory; Karp's 1972 paper reduced SAT to 21 other combinatorial problems (Clique, Vertex Cover, Hamiltonian Cycle), establishing NP-completeness as pervasive.

Corollary

3-SAT (each clause has exactly 3 literals) remains NP-complete via simple reduction from SAT (splitting long clauses with auxiliary variables).