Theory of computation and complexity
10 papers, 1936 to 1997.
- On Computable Numbers, with an Application to the Entscheidungsproblem
the universal machine and the undecidability of the halting problem
- A Mathematical Theory of Communication
entropy, channel capacity, and the separation of source and channel coding
- Error Detecting and Error Correcting Codes
minimum distance, and codes that repair what they detect
- Finite Automata and Their Decision Problems
nondeterministic automata, and the subset construction that removes it
- Relationships Between Nondeterministic and Deterministic Tape Complexities
Savitch's theorem: NSPACE(f) is in DSPACE(f squared)
- The Complexity of Theorem-Proving Procedures
NP-completeness, and SAT as the first complete problem
- Reducibility Among Combinatorial Problems
twenty-one problems reduced to one another, making NP-completeness a tool
- The Knowledge Complexity of Interactive Proof-Systems
interactive proofs, and proving a statement while revealing nothing else
- IP = PSPACE
interaction with randomness buys exactly polynomial space
- Natural Proofs
why the circuit lower-bound techniques that existed could not settle P vs NP