Computational complexity
หน้านี้สำหรับรายวิชา computational complexity
หนังสือที่จะใช้คือ Arora & Barak, Computational Complexity: A Modern Approach, Cambridge University Press.
เนื้อหา
- NP and NP completeness
- Diagonalization
- Space complexity
- The polynomial hierarchy and alternations
- Circuits
- Randomized computation
- Interactive proofs
- Communication complexity
- Derandomization, expanders and extractors
- Hardness amplification and error correcting codes
- PCP
- Quantum computation (maybe)
