Theory of Computation (CS422) in Spring 2019 at KAIST

The Theory of Computation provides a sound logical foundation to computer science. By comparing various formal models of computation with respect to their capabilities, it identifies both fundamental features and ultimate limitations of contemporary digital computing machinery. Rigorous notions of efficiency are captured by famous complexity classes such as P and PSPACE; and concepts like oracles or polynomial-time reduction permit to compare computational problems with respect to their algorithmic cost: NP-hardness results thus serve as 'beacons' of intractability.

• Lecturer: Martin Ziegler
• Schedule: Mondays and Wednesdays, 13:00 to 14:15
• Location: N1 #112
• TA: Ivan Koswara
• Office hours: Mondays 15:00 to 16:00 in E3-1 #2450
• Language: English
• Grading: Homework 30%, Attendance 10%, Midterm exam 30%, Final exam 30%
• Attendance: 10 points for missing less than 5 lectures, 9 when missing 5 lectures, and so on. 14 or more missed lectures earn you no attendance points.
• Midterm exam on Monday, April 15 from 13:00 to 15:45 in N1 #112
• Final exam on Monday, June 10 from 13:00 to 15:45 in N1 #112

We make a special pedagogical effort to avoid the arduous Turing machine formalism and instead employ a variant of WHILE programs.

I. Motivating Examples (ppt, pdf):

• comparison-based sorting
• finite automata
• asymptotic cost
• addition chain
• matrix multiplication
• diagonalization / undecidable Halting Problem

II. Basic Computability Theory (ppt, pdf):

• Un-/Semi-Decidability and Enumerability
• Reduction, degrees of undecidabiliy
• Busy Beaver/Rado function
• LOOP programs
• and their capabilities (pdf)
• Ackermann's Function

III. Advanced Computability (ppt, pdf):

• WHILE programs
• UTM Theorem
• Normal Form Theorem
• SMN Theorem / Currying (Schönfinkeling)
• Recursion Theorem, Fixedpoint Theorem, QUINES
• Oracle WHILE Programs, Post/Friedberg/Muchnik (pdf)
• Arithmetic Hierarchy
• (Post's Correspondence Problem, truth of arithmetic formulae)

IV. Computational Complexity (ppt, pdf):

• Model of computation with (bit) cost: WHILE+
• Complexity classes P, NP, PSPACE, EXP
• and their inclusion relations
• nondeterministic WHILE+ programs
• Example problems: Euler Circuit, Edge Cover
• Example problems: Hamiltonian Circuit, Vertex Cover, Independent Set, Clique, Boolean Satisfiability, Integer Linear Programming
• Boolean formulas (ppt, pdf)

V. Structural Complexity / NPc (ppt, pdf):

• polynomial-time reductions
• equivalent problems Clique, Independent Set, Boolean Satisfiability, 3-Satisfiability
• Cook-Levin Theorem, Master Reduction
• Ladner's Theorem (without proof)

VI. PSPACE and Polynomial Hierarchy (ppt, pdf):

• PSPACE-completeness
• QBF, 3QBF, GRAPH
• Savitch's Theorem
• Oracle Computation
• Quantifier Alternations

VII. Advanced Complexity (ppt, pdf):

• (Time Hierarchy)
• complexity of cryptography: UP and one-way functions
• (counting problems, Toda's Theorem)
• (LOGSPACE, Immerman-Szelepcsenyi Theorem)
• (Approximation algorithms and hardness)
• (randomized algorithms, probability amplification, BPP, Adleman and Sipser-Gacs-Lautemann Theorems)

Regularly recalling, applying, and extending the definitions, theorems, and proofs from the lecture is essential for comprehension and successful study. Therefore consider it as a courtesy that we will create homework assignments and publish them on this web page.

Homework submissions are to be submitted on the deadline day, by 13:10 (before class, with a grace period).

If you're late, you can submit after class, or by going to building E3-1 room #2450 (if it's Monday) or #3413 (if it's Wednesday), up to 16:00, with 50% penalty. After that we will not accept late submissions for the homework.

If you are unable to come to class for whatever reason, you may submit it earlier by going to E3-1 room #3413, or you may ask a friend to submit it for you during class.

You must print and sign the Honor Code and submit it along with your first homework submission. As long as your Honor Code is missing, we will not grade your homework submissions.

1. Homework 1 and Honor Code (given 3/4, due 3/11)
2. Homework 2 (given 3/18, due 3/25)
3. Homework 3 (given 4/10, due 4/24)
4. Homework 4 (given 5/2, due 5/13)
5. Homework 5 (given 5/20, due 5/27)
6. Homework 6 (given 5/28, due 6/5)

Copied solutions receive 0 points and personal interrogation during office/claiming hours.
Cheating during the exam results in failed grade F.
You are to sign and submit a pledge of integrity with your first written homework solution.

• Papadimitriou: Computational Complexity, Addison Wesley (1993)
• Moore, Mertens: The Nature of Computation (2011)
• Lewis, Papadimitrou: Elements of the Theory of Computation (2nd. ed.), Prentice-Hall (1997).
• Arora, Barak: Computational Complexity - A Modern Approach, Cambridge University Press (2009).
• Sipser: Introduction to the Theory of Computation, PWS Publishing (1997).
• Enderton: Computability Theory (2011).

You are expected to buy some of these (or similar) books — latest for the midterm exam: leaving you enough time to first thoroughly browse and compare them in the library.

* KLMS