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-10-28] – [Synopsis/Syllabus:] Martin Ziegler21cs422 [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/Hamiltonian Circuit, Edge/Vertex Cover
-  * Example problems: Hamiltonian Circuit, Vertex Cover, Independent Set, Clique, Integer Linear Programming+
   * 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}}, {{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 =====