Levin's theorem (NP-completeness)

Statement

Levin independently proved that SAT and other "universal search problems" are NP-complete. His 1973 paper "Universal search problems" (in Russian) established the same result as Cook (1971), using a different framework—search problems and optimal algorithms. The theorem is the cornerstone of complexity theory.

Formula

SAT is NP-complete

Equation

∀L ∈ NP: L ≤ₚ SAT

Proof sketch

Levin framed NP-completeness via "universal search problems"—problems for which an optimal algorithm exists. He showed that tiling, SAT, and other combinatorial problems are complete for this class. The proof encodes nondeterministic computation; the result is equivalent to Cook's.