Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| 19cs422 [2019-05-28] – [Homework/Assignments] Ivan Koswara | 19cs422 [2019-06-09] (current) – Martin Ziegler | ||
|---|---|---|---|
| Line 59: | Line 59: | ||
| * Ladner' | * Ladner' | ||
| - | VI. PSPACE and Polynomial Hierarchy | + | VI. PSPACE and Polynomial Hierarchy |
| * PSPACE-completeness | * PSPACE-completeness | ||
| * QBF, 3QBF, GRAPH | * QBF, 3QBF, GRAPH | ||
| Line 66: | Line 66: | ||
| * Quantifier Alternations | * Quantifier Alternations | ||
| - | VII. Advanced Complexity | + | VII. Advanced Complexity |
| - | * Time Hierarchy | + | * (Time Hierarchy) |
| * complexity of cryptography: | * complexity of cryptography: | ||
| - | * counting problems, Toda's Theorem | + | * (counting problems, Toda's Theorem) |
| - | * LOGSPACE, Immerman-Szelepcsenyi Theorem | + | * (LOGSPACE, Immerman-Szelepcsenyi Theorem) |
| - | * Approximation algorithms and hardness | + | * (Approximation algorithms and hardness) |
| - | * randomized algorithms, probability amplification, | + | * (randomized algorithms, probability amplification, |
| ===== Homework/ | ===== Homework/ | ||