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