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-04-07] – [Synopsis/Syllabus:] Ivan Koswara19cs422 [2019-06-09] (current) – Martin Ziegler
Line 29: Line 29:
   * Un-/Semi-Decidability and Enumerability   * Un-/Semi-Decidability and Enumerability
   * Reduction, degrees of undecidabiliy   * Reduction, degrees of undecidabiliy
-  * (Busy Beaver function)+  * Busy Beaver/Rado function
   * LOOP programs   * LOOP programs
   * and their capabilities ({{:lectures:2019:cs422:0327.pdf|pdf}})   * and their capabilities ({{:lectures:2019:cs422:0327.pdf|pdf}})
Line 41: Line 41:
   * Recursion Theorem, Fixedpoint Theorem, QUINES   * Recursion Theorem, Fixedpoint Theorem, QUINES
   * Oracle WHILE Programs, Post/Friedberg/Muchnik ({{:lectures:2019:cs422:0408.pdf|pdf}})   * Oracle WHILE Programs, Post/Friedberg/Muchnik ({{:lectures:2019:cs422:0408.pdf|pdf}})
 +  * Arithmetic Hierarchy
   * (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 57: 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 64: 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 85: 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: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. \\