Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
19cs422 [2019-04-10] – [Homework/Assignments] Martin Ziegler | 19cs422 [2019-06-09] (current) – Martin Ziegler | ||
---|---|---|---|
Line 29: | Line 29: | ||
* Un-/ | * Un-/ | ||
* Reduction, degrees of undecidabiliy | * Reduction, degrees of undecidabiliy | ||
- | * (Busy Beaver function) | + | * Busy Beaver/Rado function |
* LOOP programs | * LOOP programs | ||
* and their capabilities ({{: | * and their capabilities ({{: | ||
Line 44: | Line 44: | ||
* (Post' | * (Post' | ||
- | IV. Computational Complexity | + | IV. Computational Complexity |
* Model of computation with (bit) cost: WHILE+ | * Model of computation with (bit) cost: WHILE+ | ||
* Complexity classes P, NP, PSPACE, EXP | * Complexity classes P, NP, PSPACE, EXP | ||
* and their inclusion relations | * and their inclusion relations | ||
* nondeterministic WHILE+ programs | * nondeterministic WHILE+ programs | ||
- | * Example problems: Euler Circuit, Edge Cover, | + | * Example problems: Euler Circuit, Edge Cover |
* Example problems: Hamiltonian Circuit, Vertex Cover, Independent Set, Clique, Boolean Satisfiability, | * Example problems: Hamiltonian Circuit, Vertex Cover, Independent Set, Clique, Boolean Satisfiability, | ||
+ | * Boolean formulas ({{ : | ||
- | V. Structural Complexity / NPc | + | V. Structural Complexity / NPc ({{19cs422e.ppt|ppt}}, |
* polynomial-time reductions | * polynomial-time reductions | ||
* equivalent problems Clique, Independent Set, Boolean Satisfiability, | * equivalent problems Clique, Independent Set, Boolean Satisfiability, | ||
Line 58: | 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 65: | 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/ | ||
Line 86: | Line 87: | ||
- {{ : | - {{ : | ||
- {{ : | - {{ : | ||
- | - {{ : | + | - {{ : |
+ | - {{ : | ||
+ | - {{ : | ||
+ | - {{ : | ||
===== Academic Honesty ===== | ===== Academic Honesty ===== | ||
Copied solutions receive 0 points and personal interrogation during office/ | Copied solutions receive 0 points and personal interrogation during office/ |