Proof — Karp's 21 NP-complete problems

Statement

Using Cook's result that SAT is NP-complete, Karp showed polynomial-time reductions from SAT to 21 combinatorial problems—clique, vertex cover, Hamiltonian cycle, graph coloring, knapsack, partition, and others. Each is NP-complete; Karp reduction (many-one) became the standard technique.

Formula

SAT ≤ₚ L for 21 problems L

Equation

Clique, Vertex Cover, Hamiltonian Cycle, TSP, ...

Proof sketch

Karp (1972) gave polynomial-time many-one reductions from SAT to each of 21 problems. If any has a poly-time algorithm, all do. Introduced the formal notion of Karp reduction. Built on Cook's 1971 theorem.