[Computational Complexity] Foundations of Complexity
- In the first year of this blog I wrote a series of "lessons" to give an informal introduction to computational complexity but I never wrote a single post that links to them all.
I hope to add more lessons in the future.
- What is a Computer?
- Computable and Computably Enumerable Languages
- Universal Turing Machines and Diagonalization
- Noncomputable Computably Enumerable Languages
- The Halting Problem
- The Recursion Theorem
- Efficient Computation
- The P versus NP Problem
- Turing Machine Redux
- CNF-SAT is NP-complete
- More NP-complete Problems
- Ladner's Theorem
- Space Complexity
- Savitch's Theorem
- The Immerman-Szelepcsényi Theorem
Posted By Lance to Computational Complexity at 5/01/2009 07:40:00 AM