[Computational Complexity] Favorite Theorems: Second Decade Recap
This past year I listed my favorite computational complexity theorems from 1975-1984.
- Alternation (Chandra-Kozen-Stockmeyer)
- Relativization (Baker-Gill-Solovay)
- Small Sets (Mahaney)
- Primality Algorithms (Solovay-Strassen, Miller, Rabin)
- Probabilistic Complexity (Gill, Sipser)
- The Permanent (Valiant)
- Unique Witnesses (Valiant-Vazirani)
- Parity (Furst-Saxe-Sipser, Ajtai)
- The Yao Principle (Yao)
- Nonuniform Complexity (Karp-Lipton)
Next favorite theorems in 2014. Will your name be on that list?
Posted by Lance to Computational Complexity at 12/11/2006 11:11:00 AM