The Dawn of Computational Complexity Theory
Talkat 50 Years of Satisfiability: The Centrality of SAT in the Theory of Computing · 2021-02-11..05-13
summary
Starts from Cook 1971 proving satisfiability’s central role and shows a concrete method: polynomial-time reductions that tie many problems’ fate to SAT, producing 21 NP-complete problems in the original paper and a reduction cascade that now covers thousands. Traces earlier algorithmic work (simplex, Gomory cutting planes, Dantzig Fulkerson Johnson’s 49‑city TSP) and later breakthroughs (Miller‑Rabin, AKS) and highlights a persistent puzzle: why resolution/CDCL solvers with simple primitives solve industrial SAT instances far beyond worst‑case theory.
AI-written summary · about