ผลต่างระหว่างรุ่นของ "Computational complexity"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) (สร้างหน้าด้วย "หน้านี้สำหรับรายวิชา computational complexity หนังสือที่จะใช้คือ Arora & Bar...") |
Jittat (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 2 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 4: | แถว 4: | ||
== เนื้อหา == | == เนื้อหา == | ||
| + | * 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) | ||
| + | |||
| + | == การบ้าน == | ||
| + | * [[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)
