Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
21cs422 [2021-09-13] – Martin Ziegler | 21cs422 [2021-11-30] (current) – [Synopsis/Syllabus:] Martin Ziegler | ||
---|---|---|---|
Line 19: | Line 19: | ||
* Un-/ | * Un-/ | ||
* Reduction, degrees of undecidabiliy | * Reduction, degrees of undecidabiliy | ||
- | * Busy Beaver/Rado function | + | |
+ | | ||
+ | * Ackermann' | ||
* LOOP programs | * LOOP programs | ||
* and their capabilities | * and their capabilities | ||
- | * Ackermann' | ||
II. Advanced Computability ({{cs422b.ppt|ppt}}, | II. Advanced Computability ({{cs422b.ppt|ppt}}, | ||
Line 30: | Line 31: | ||
* SMN Theorem / Currying (Schönfinkeling) | * SMN Theorem / Currying (Schönfinkeling) | ||
* Recursion Theorem, Fixedpoint Theorem, QUINES | * Recursion Theorem, Fixedpoint Theorem, QUINES | ||
- | * Oracle WHILE Programs, Post/ | + | * Oracle WHILE Programs |
* Arithmetic Hierarchy | * Arithmetic Hierarchy | ||
- | * (Post's Correspondence Problem, truth of arithmetic formulae) | + | * Post/ |
III. Computational Complexity ({{cs422c.ppt|ppt}}, | III. Computational Complexity ({{cs422c.ppt|ppt}}, | ||
Line 38: | 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/ | ||
+ | * Boolean formulas and Satisfiability | ||
* nondeterministic WHILE+ programs | * nondeterministic WHILE+ programs | ||
- | * Example problems: Euler Circuit, Edge Cover | + | * Time Hierarchy Theorem: P≠EXP |
- | * Example problems: Hamiltonian Circuit, Vertex Cover, Independent Set, Clique, Boolean Satisfiability, | + | |
- | * Boolean formulas | + | |
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}}, | ||
- | * PSPACE-completeness | + | * PSPACE |
- | * QBF, 3QBF, GRAPH | + | * Master Reduction |
- | * Savitch' | + | * A PSPACE-complete Two-Player Game on Digraphs |
- | * Oracle | + | * Savitch' |
- | * Quantifier Alternations | + | * Immerman-Szelepcsényi: |
+ | * Oracle | ||
+ | * 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/ |