ผลต่างระหว่างรุ่นของ "Computational complexity"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 19: | แถว 19: | ||
== การบ้าน == | == การบ้าน == | ||
* [[Computational complexity/hw1|การบ้าน 1]] | * [[Computational complexity/hw1|การบ้าน 1]] | ||
| + | * [[Computational complexity/hw2|การบ้าน 2]] | ||
| + | |||
| + | * [[Computational complexity/paper list|รายการเปเปอร์วิจัย]] | ||
รุ่นแก้ไขปัจจุบันเมื่อ 21:16, 11 พฤษภาคม 2564
หน้านี้สำหรับรายวิชา 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)
