Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
21cs422 [2021-09-07] – [E-Learning] Martin Ziegler21cs422 [2021-11-30] (current) – [Synopsis/Syllabus:] Martin Ziegler
Line 15: Line 15:
  
 0. Motivation  0. Motivation 
 +
 I. Basic Computability Theory ({{cs422a.ppt|ppt}}, {{cs422a.pdf|pdf}}): I. Basic Computability Theory ({{cs422a.ppt|ppt}}, {{cs422a.pdf|pdf}}):
   * Un-/Semi-Decidability and Enumerability   * Un-/Semi-Decidability and Enumerability
   * Reduction, degrees of undecidabiliy   * Reduction, degrees of undecidabiliy
-  * Busy Beaver/Rado function+  * (Post's Correspondence Problem, truth of arithmetic formulae) 
 +  * Busy Beaver function 
 +  * Ackermann's Function
   * LOOP programs   * LOOP programs
   * and their capabilities    * and their capabilities 
-  * Ackermann's Function 
  
 II. Advanced Computability ({{cs422b.ppt|ppt}}, {{cs422b.pdf|pdf}}): II. Advanced Computability ({{cs422b.ppt|ppt}}, {{cs422b.pdf|pdf}}):
Line 29: 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/Friedberg/Muchnik +  * Oracle WHILE Programs
   * Arithmetic Hierarchy   * Arithmetic Hierarchy
-  * (Post's Correspondence Problem, truth of arithmetic formulae)+  * Post/Friedberg/Muchnik 
  
 III. Computational Complexity ({{cs422c.ppt|ppt}}, {{cs422c.pdf|pdf}}): III. Computational Complexity ({{cs422c.ppt|ppt}}, {{cs422c.pdf|pdf}}):
Line 37: 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/Hamiltonian Circuit, Edge/Vertex Cover
 +  * 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, Integer Linear Programming +
-  * Boolean formulas +
  
 IV. Structural Complexity / NPc ({{cs422d.ppt|ppt}}, {{cs422d.pdf|pdf}}): IV. Structural Complexity / NPc ({{cs422d.ppt|ppt}}, {{cs422d.pdf|pdf}}):
-  * polynomial-time reductions +  * polynomial-time reduction 
-  * equivalent problems Clique, Independent Set, Boolean Satisfiability, 3-Satisfiability+  * equivalent problems: Clique = Independent Set <= Boolean Satisfiability <= 3-Satisfiability <= Independent Set
   * Cook-Levin Theorem, Master Reduction   * Cook-Levin Theorem, Master Reduction
-  * Ladner's Theorem +  * Bin Packing is NP-complete 
 +  * Scenarios for P/NP, Ladner's Theorem 
  
 V. PSPACE and Polynomial Hierarchy ({{cs422e.ppt|ppt}}, {{cs422e.pdf|pdf}}): V. PSPACE and Polynomial Hierarchy ({{cs422e.ppt|ppt}}, {{cs422e.pdf|pdf}}):
-  * PSPACE-completeness +  * PSPACE and QBF 
-  * QBF, 3QBF, GRAPH +  * Master Reduction 
-  * Savitch's Theorem +  * A PSPACE-complete Two-Player Game on Digraphs 
-  * Oracle Computation +  * Savitch's Theorem: NSPACE(f) in SPACE(f²) 
-  * Quantifier Alternations+  * Immerman-Szelepcsényi: NSPACE(f) = coNSPACE(f) 
 +  * Oracle Complexity and Polynomial Hierarchy, Semantically and Syntactically 
 +  * Limitations of Relativizing Proofs: Baker, Gill & Solovay;  Bennett & Gill 
  
-VI. Advanced Complexity  ({{cs422f.ppt|ppt}}, {{cs422f.pdf|pdf}}): +VI. Perspectives ({{cs422f.ppt|ppt}}, {{cs422f.pdf|pdf}}):
-  * (Time Hierarchy)+
   * complexity of cryptography: UP and one-way functions   * complexity of cryptography: UP and one-way functions
-  * (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, BPP, Adleman and Sipser-Gacs-Lautemann Theorems 
-  * (randomized algorithms, probability amplification, BPP, Adleman and Sipser-Gacs-Lautemann Theorems)+  * fixed-parameter tractability and hardness
  
 ===== Homework/Assignments =====  ===== Homework/Assignments ===== 
Line 83: Line 87:
  
 ===== E-Learning =====  ===== E-Learning ===== 
- * [[https://www.youtube.com/playlist?list=PLvcvykdwsGNG3TUu_dPMLdXMjVxLKpbzf|YouTube]] +   * [[https://www.youtube.com/playlist?list=PLvcvykdwsGNG3TUu_dPMLdXMjVxLKpbzf|YouTube]] 
- * [[https://klms.kaist.ac.kr/course/view.php?id=130178|KLMS]]  +   * [[https://klms.kaist.ac.kr/course/view.php?id=130178|KLMS]]  
- * Due to the large number (>80) of students enrolled, we unfortunately cannot answer questions by email.+   * 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. Instead please use the KLMS Bulletin Board or visit the TAs during their office hours.