Computational Complexity: A Modern Approach > 계산이론

Part I. Basic Complexity Classes:
1. The computational model - and why it doesn\'t matter;
2. NP and NP completeness;
3. Diagonalization;
4. Space complexity;
5. The polynomial hierarchy and alternations;
6. Boolean circuits;
7. Randomized computation;
8. Interactive proofs;
9. Cryptography;
10. Quantum computation;
11. PCP theorem and hardness of approximation: an introduction;

Part II. Lower Bounds for Concrete Computational Models:
12. Decision trees;
13. Communication complexity;
14. Circuit lower bounds;
15. Proof complexity;
16. Algebraic computation models;

Part III. Advanced Topics:
17. Complexity of counting;
18. Average case complexity: Levin\'s theory;
19. Hardness amplification and error correcting codes;
20. Derandomization;
21. Pseudorandom constructions: expanders and extractors;
22. Proofs of PCP theorems and the Fourier transform technique;
23. Why are circuit lower bounds so difficult?;
Appendix A: mathematical background.