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. 

1. What is a Computer?
2. Computable and Computably Enumerable Languages
3. Universal Turing Machines and Diagonalization
4. Noncomputable Computably Enumerable Languages
5. Reductions
6. The Halting Problem
7. The Recursion Theorem
8. Efficient Computation
9. Nondeterminism
10. The P versus NP Problem
11. NP-Completeness
12. Turing Machine Redux
13. Satisfiability
14. CNF-SAT is NP-complete
15. More NP-complete Problems
16. Ladner's Theorem 
17. Space Complexity
18. Savitch's Theorem
19. The Immerman-Szelepcsényi Theorem

I hope to add more lessons in the future.