Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| 21cs422 [2021-11-23] – [Synopsis/Syllabus:] Martin Ziegler | 21cs422 [2021-11-30] (current) – [Synopsis/Syllabus:] Martin Ziegler | ||
|---|---|---|---|
| Line 39: | Line 39: | ||
| * Complexity classes P, NP, PSPACE, EXP | * Complexity classes P, NP, PSPACE, EXP | ||
| * and their inclusion relations | * and their inclusion relations | ||
| - | * Example problems: Euler Circuit, Edge Cover | + | * Example problems: Euler/ |
| - | * Example problems: Hamiltonian Circuit, | + | |
| * Boolean formulas and Satisfiability | * Boolean formulas and Satisfiability | ||
| * nondeterministic WHILE+ programs | * nondeterministic WHILE+ programs | ||
| - | * (Time) Hierarchy Theorem: P≠EXP | + | * Time Hierarchy Theorem: P≠EXP |
| IV. Structural Complexity / NPc ({{cs422d.ppt|ppt}}, | IV. Structural Complexity / NPc ({{cs422d.ppt|ppt}}, | ||
| - | * polynomial-time | + | * polynomial-time |
| - | * equivalent problems Clique, Independent Set, Boolean Satisfiability, 3-Satisfiability | + | * equivalent problems: Clique |
| * Cook-Levin Theorem, Master Reduction | * Cook-Levin Theorem, Master Reduction | ||
| - | * Ladner' | + | * Bin Packing is NP-complete |
| + | * Scenarios for P/NP, Ladner' | ||
| V. PSPACE and Polynomial Hierarchy ({{cs422e.ppt|ppt}}, | V. PSPACE and Polynomial Hierarchy ({{cs422e.ppt|ppt}}, | ||
| Line 60: | Line 60: | ||
| * Limitations of Relativizing Proofs: Baker, Gill & Solovay; | * Limitations of Relativizing Proofs: Baker, Gill & Solovay; | ||
| - | VI. Advanced Complexity | + | VI. Perspectives |
| - | * (Time Hierarchy) | + | |
| * complexity of cryptography: | * complexity of cryptography: | ||
| - | * (counting problems, Toda's Theorem) | + | * counting problems: #P and Toda's Theorem |
| - | * (LOGSPACE, Immerman-Szelepcsenyi Theorem) | + | * Approximation algorithms and hardness |
| - | * (Approximation algorithms and hardness) | + | * randomized algorithms, probability amplification, |
| - | * (randomized algorithms, probability amplification, | + | * fixed-parameter tractability and hardness |
| ===== Homework/ | ===== Homework/ | ||