The Dawn of Computational Complexity Theory | From the Archive

In 2021, the Simons Institute hosted a workshop titled 50 Years of Satisfiability: The Centrality of SAT in the Theory of Computing. One of the talks was by Simons Institute Founding Director Richard Karp, who gave a firsthand account of early developments in computational complexity theory from the time he earned his PhD in 1959 to the publication of Cook’s seminal 1971 paper, “The Complexity of Theorem-Proving Procedures,” and beyond.