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-05] – [Theory of Computation (CS422) in Spring 2019 at KAIST] Martin Ziegler19cs422 [2019-06-03] – 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}})
   * Ackermann's Function   * Ackermann's Function
  
Line 40: Line 40:
   * SMN Theorem / Currying (Schönfinkeling)   * SMN Theorem / Currying (Schönfinkeling)
   * Recursion Theorem, Fixedpoint Theorem, QUINES   * Recursion Theorem, Fixedpoint Theorem, QUINES
-  * Oracle WHILE Programs, Post/Friedberg/Muchnik+  * 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 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. \\