0. Notational conventions
1. The computacional model- and why it doesn’t matter.
2. NP and NP complétense.
3. Diagonalization.
4. Space complexity.
5. The polinomial hierarchy and alternations.
6. Boolean circuits.
7. Randomized computation.
8. Interactive Prof..
9. Cryptography.
10. Quantum computation.
11. PCP theorem and hardness of approximation: An introduction.
12. Decision trees.
13. Comunication complexity.
14. Circuit lower bpunds: Complexity theory’s Waterloo.
15. Proof complexity.
16. Algebraic computation models.
17. Complexity of counting.
18. Average case complexity: Levin’s theory.
19. Hardness amplification and error-correcting codes.
20. Derandomization.
21. Pseudorandom constructions: Expander and extractors.
22. Proof of PCP theorems and the Fourier transform technique.
23. Why are circuit lower bounds so difficult?
Appendix: Mathematical background.