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
19cs422 [2019-04-13] – [Synopsis/Syllabus:] Martin Ziegler19cs422 [2019-06-03] – Martin Ziegler
Line 44: Line 44:
   * (Post's Correspondence Problem, truth of arithmetic formulae)   * (Post's Correspondence Problem, truth of arithmetic formulae)
  
-IV. Computational Complexity+IV. Computational Complexity ({{19cs422d.ppt|ppt}}, {{19cs422d.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
   * 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 86: Line 87:
   - {{ :lectures:2019:cs422:hw1.pdf |Homework 1}} and {{ :lectures:2019:cs422:honorcode.pdf |Honor Code}} (given 3/4, due 3/11)   - {{ :lectures:2019:cs422:hw1.pdf |Homework 1}} and {{ :lectures:2019:cs422:honorcode.pdf |Honor Code}} (given 3/4, due 3/11)
   - {{ :lectures:2019:cs422:hw2.pdf |Homework 2}} (given 3/18, due 3/25)   - {{ :lectures:2019:cs422:hw2.pdf |Homework 2}} (given 3/18, due 3/25)
-  -  {{ :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: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. \\