Cook–Levin theorem

Statement

The Boolean satisfiability problem (SAT) is NP-complete. Any problem in NP can be reduced to SAT in polynomial time. Cook (1971) proved this at STOC; Levin (1973) independently proved the same result in the Soviet Union. Both established the first NP-complete problem.

Formula

SAT is NP-complete

Equation

∀L ∈ NP: L ≤ₚ SAT

Proof sketch

Cook showed that every nondeterministic Turing machine running in polynomial time can be simulated by a polynomial-time reduction to SAT. Levin independently proved the same result in the Soviet Union. The proof encodes the computation of an NP machine as a Boolean formula whose satisfiability corresponds to acceptance.