After I choose my ten favorite theorems in the decades 1985-1994 and 1995-2004, I went back to the first decade in complexity. Here is a recap of my ten favorite theorems in computational complexity from 1965-1974. - The Seminal Paper (Hartmanis-Stearns)
- Efficient Computation (Cobham-Edmonds)
- NP-Completeness (Cook)
- Combinatorial NP-Complete Problems (Karp)
- The Polynomial-Time Hierarchy (Meyer-Stockmeyer)
- P = NP for Space (Savitch)
- Abstract Complexity (Blum)
- NP-Incomplete Sets (Ladner)
- Logical Characterization of NP (Fagin)
- Defining the Future (Cook-Reckhow)

We have one missing decade, so some more list making next year.

--

Posted by Lance to Computational Complexity at 12/19/2005 07:31:00 AM