ผลต่างระหว่างรุ่นของ "Computational complexity"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 1 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 16: | แถว 16: | ||
* PCP | * PCP | ||
* Quantum computation (maybe) | * Quantum computation (maybe) | ||
| + | |||
| + | == การบ้าน == | ||
| + | * [[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)
