The Cook-Levin Theorem
The Cook-Levin theorem proves that Boolean satisfiability is NP-complete, giving the first natural NP-complete problem.
The statement
The Cook-Levin theorem, proved independently by Stephen Cook and Leonid Levin around 1971, states that the Boolean satisfiability problem (SAT) is NP-complete. It is in NP, and every problem in NP reduces to it in polynomial time.
The idea of the proof
Take any problem in NP, solved by some polynomial-time nondeterministic Turing machine. The proof builds a Boolean formula that is satisfiable exactly when that machine has an accepting computation on the given input. The formula's variables encode the machine's tape, head, and state at each time step.
Encoding a computation
- Variables describe which symbol is in each tape cell at each step
- Clauses enforce that each step follows the machine's transition rules
- Clauses require a valid start configuration and an accepting end
- A satisfying assignment is a valid accepting computation
Why it is foundational
Before Cook-Levin there was no known natural problem to which all of NP reduced. Afterward, SAT became the anchor. To prove any other problem NP-complete, you reduce SAT (or a descendant) to it, rather than reasoning about all NP machines directly.
The cascade that followed
Within a few years Richard Karp showed 21 classic problems NP-complete by reducing from SAT, including clique, vertex cover, and the traveling salesman decision problem. The list has since grown into the thousands, all traceable back to this one theorem.
What it means for P vs NP
Because everything in NP reduces to SAT, a polynomial-time SAT algorithm would place all of NP in P, settling P vs NP. The theorem thus concentrates the entire question into the tractability of a single, concrete problem about logical formulas.