Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| 21cs422 [2021-07-30] – created Martin Ziegler | 21cs422 [2021-11-30] (current) – [Synopsis/Syllabus:] Martin Ziegler | ||
|---|---|---|---|
| Line 14: | Line 14: | ||
| We make a special pedagogical effort to avoid the arduous Turing machine formalism and instead employ a variant of WHILE programs. | We make a special pedagogical effort to avoid the arduous Turing machine formalism and instead employ a variant of WHILE programs. | ||
| - | I. Motivating Examples ({{cs422a.ppt|ppt}}, | + | 0. Motivation |
| - | * comparison-based sorting | + | |
| - | * finite automata | + | |
| - | * asymptotic cost | + | |
| - | * addition chain | + | |
| - | * matrix multiplication | + | |
| - | * diagonalization / undecidable Halting Problem | + | |
| - | II. Basic Computability Theory ({{cs422b.ppt|ppt}}, {{cs422b.pdf|pdf}}): | + | I. Basic Computability Theory ({{cs422a.ppt|ppt}}, {{cs422a.pdf|pdf}}): |
| * 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' | ||
| - | III. Advanced Computability ({{cs422c.ppt|ppt}}, {{cs422c.pdf|pdf}}): | + | II. Advanced Computability ({{cs422b.ppt|ppt}}, {{cs422b.pdf|pdf}}): |
| * WHILE programs | * WHILE programs | ||
| * UTM Theorem | * UTM Theorem | ||
| Line 36: | 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/ |
| - | IV. Computational Complexity ({{cs422d.ppt|ppt}}, {{cs422d.pdf|pdf}}): | + | III. Computational Complexity ({{cs422c.ppt|ppt}}, {{cs422c.pdf|pdf}}): |
| * 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 | ||
| + | * 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 | + | |
| - | V. Structural Complexity / NPc ({{cs422e.ppt|ppt}}, {{cs422e.pdf|pdf}}): | + | IV. Structural Complexity / NPc ({{cs422d.ppt|ppt}}, {{cs422d.pdf|pdf}}): |
| - | * 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' | ||
| - | VI. PSPACE and Polynomial Hierarchy ({{cs422f.ppt|ppt}}, {{cs422f.pdf|pdf}}): | + | V. PSPACE and Polynomial Hierarchy ({{cs422e.ppt|ppt}}, {{cs422e.pdf|pdf}}): |
| - | * 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; | ||
| - | VII. 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/ | ||
| Line 90: | Line 87: | ||
| ===== E-Learning ===== | ===== E-Learning ===== | ||
| - | * [[http:// | + | * [[https:// |
| + | * [[https:// | ||
| + | * Due to the large number (>80) of students enrolled, we unfortunately cannot answer questions by email. \\ | ||
| + | Instead please use the KLMS Bulletin Board or visit the TAs during their office hours. | ||