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)

การบ้าน

• การบ้าน 1