Theory of Computation (CS422) in Fall 2015 at KAIST's School of Computing

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
Lectures: classroom #111 in building N1
Schedule: Tuesdays and Thursdays 2:30pm to 3:45pm
Language: English
Teaching Assistant: 김미진
Office hours: Tuesdays and Thursdays 16:00 to 17:15 N1 #403
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.
Grading: The final grade will be composed as follows (small changes reserved): Homework 20%, Midterm exam 30%, Final exam 40%, Attendance 10%.
Exams: There will be a midterm exam (Oct 22nd 13h00 to 15h30) and a final exam (Dec 17, 13h00 to 15h30).

Synopsis

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

Motivation and Examples:
- Models of Computation, Algorithms, In-/Computability, Complexity
- Mathematical recap: sets, relations, functions, Hilbert's Hotel
- Unsolvability arguments: pigeon hole, sqrt(2), Cantor diagonalization, reduction
- Binary Branching Trees for Sorting, Finite Automata for Formal Languages, Addition Chains, Straight-Line Programs for Matrix Multiplication
- Undecidable Halting Problem
Computability Theory
- Un-/Semi-Decidability and Enumerability
- Reduction, more undecidable problems
- LOOP programs, simulating addition/subtraction/multiplication/division/IF-THEN-ELSE/stacks/arrays
- Ackermann's Function, runtime bounds, limit of computability
- WHILE programs, UTM and SMN Theorems, Kleene normal form
- Recursion Theorem, Fixedpoint Theorem, QUINES
- More undecidability: Post's Correspondence Problem, truth of arithmetic formulae
Complexity Theory
- asymptotic algorithmic cost, ressource-bounded complexity theory, P, PSPACE, EXP with inclusions; Hierarchy Theorems
- SAT, 2SAT, 3SAT, 4SAT, Hamiltonian Circuit, Vertex Cover, Edge Cover, Hamilton Circuit, Euler Circuit, TSP
- polynomial-time reductions, equivalent problems; 4SAT, 3SAT, Vertex Cover, and Hamilton Circuit revisited
- nondeterminism, NP, Cook-Levin Theorem
- PSPACE-completeness
Advanced Topics
- complexity of cryptography: UP and one-way functions
- polynomial hierarchy, counting problems, Toda's Theorem
- Savitch's Theorem, Immerman-Szelepcsenyi
- Approximation algorithms and hardness
- randomized algorithms, probability amplification, BPP, Adleman and Sipser-Gacs-Lautemann Theorems

Homework/Assignments:

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: usually on every other Thursday, leaving you 11 days to prepare and turn in your solution on Tuesday before the lecture (2:29pm). This deadline is strict so that we have time to review your submissions before we discuss the assignment on Thursday!

Literature:

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).

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

E-Learning:

Piazza
Slides.
Homework assignments from Sep.3 to Sep.15
and from Sep.25 to Oct.13
and from Nov.3rd to Nov.17
and from Nov.24 to Dec.8 for download.
Remember that Problem 12 conveys the practical counterpart to our complexity-theoretic treatment of one-way functions by asking you to submit your solutions signed with your private and my private PGP key.
Quiz of Oct.8
Solution to problem 5
Midterm exam problems
Final exam problems
SMN and UTM Theorems amount to Currying as in Python and C++.