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
19cs422 [2019-05-02] – [Homework/Assignments] Ivan Koswara19cs422 [2019-06-09] (current) – Martin Ziegler
Line 49: Line 49:
   * and their inclusion relations   * and their inclusion relations
   * nondeterministic WHILE+ programs   * nondeterministic WHILE+ programs
-  * Example problems: Euler Circuit, Edge Cover,+  * Example problems: Euler Circuit, Edge Cover
   * Example problems: Hamiltonian Circuit, Vertex Cover, Independent Set, Clique, Boolean Satisfiability, Integer Linear Programming   * Example problems: Hamiltonian Circuit, Vertex Cover, Independent Set, Clique, Boolean Satisfiability, Integer Linear Programming
 +  * Boolean formulas ({{ :lectures:2019:cs422:0508.pptx |ppt}}, {{ :lectures:2019:cs422:0508.pdf |pdf}})
  
-V. Structural Complexity / NPc+V. Structural Complexity / NPc ({{19cs422e.ppt|ppt}}, {{19cs422e.pdf|pdf}}):
   * polynomial-time reductions   * polynomial-time reductions
   * equivalent problems Clique, Independent Set, Boolean Satisfiability, 3-Satisfiability   * equivalent problems Clique, Independent Set, Boolean Satisfiability, 3-Satisfiability
Line 58: Line 59:
   * Ladner's Theorem (without proof)   * Ladner's Theorem (without proof)
  
-VI. PSPACE and Polynomial Hierarchy+VI. PSPACE and Polynomial Hierarchy ({{19cs422f.ppt|ppt}}, {{19cs422f.pdf|pdf}}):
   * PSPACE-completeness   * PSPACE-completeness
   * QBF, 3QBF, GRAPH   * QBF, 3QBF, GRAPH
Line 65: Line 66:
   * Quantifier Alternations   * Quantifier Alternations
  
-VII. Advanced Complexity +VII. Advanced Complexity  ({{19cs422g.ppt|ppt}}, {{19cs422g.pdf|pdf}}): 
-  * Time Hierarchy+  * (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, Toda's Theorem) 
-  * LOGSPACE, Immerman-Szelepcsenyi 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)
  
 ===== Homework/Assignments =====  ===== Homework/Assignments ===== 
Line 88: Line 89:
   - {{ :lectures:2019:cs422:hw3.pdf |Homework 3}} (given 4/10, due 4/24)   - {{ :lectures:2019:cs422:hw3.pdf |Homework 3}} (given 4/10, due 4/24)
   - {{ :lectures:2019:cs422:hw4.pdf |Homework 4}} (given 5/2, due 5/13)   - {{ :lectures:2019:cs422:hw4.pdf |Homework 4}} (given 5/2, due 5/13)
 +  - {{ :lectures:2019:cs422:hw5.pdf |Homework 5}} (given 5/20, due 5/27)
 +  - {{ :lectures:2019:cs422:hw6.pdf |Homework 6}} (given 5/28, due 6/5)
 ===== Academic Honesty ===== ===== Academic Honesty =====
 Copied solutions receive 0 points and personal interrogation during office/claiming hours. \\ Copied solutions receive 0 points and personal interrogation during office/claiming hours. \\