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
Last revisionBoth sides next revision
21cs422 [2021-11-23] – [Synopsis/Syllabus:] Martin Ziegler21cs422 [2021-11-29] – [Synopsis/Syllabus:] Martin Ziegler
Line 43: Line 43:
   * 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}}):
Line 49: Line 49:
   * equivalent problems Clique, Independent Set, Boolean Satisfiability, 3-Satisfiability   * equivalent problems Clique, Independent Set, Boolean Satisfiability, 3-Satisfiability
   * 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 and QBF   * PSPACE and QBF
   * Master Reduction   * Master Reduction
-  * A Two-Player Game on Digraphs+  * A PSPACE-complete Two-Player Game on Digraphs
   * Savitch's Theorem: NSPACE(f) in SPACE(f²)   * Savitch's Theorem: NSPACE(f) in SPACE(f²)
   * Immerman-Szelepcsényi: NSPACE(f) = coNSPACE(f)   * Immerman-Szelepcsényi: NSPACE(f) = coNSPACE(f)
Line 60: Line 61:
   * Limitations of Relativizing Proofs: Baker, Gill & Solovay;  Bennett & Gill    * 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 =====