# Theory of Computation (CS422) in Fall 2021 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: Tuesdays and Thursdays, 16:00 to 17:30
• Location: online, via Zoom
• Language: English only
• Grading: Homework 30%, Quiz 10%, Midterm exam 30%, Final exam 30%

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

0. Motivation

I. Basic Computability Theory (ppt, pdf):

• Un-/Semi-Decidability and Enumerability
• Reduction, degrees of undecidabiliy
• (Post's Correspondence Problem, truth of arithmetic formulae)
• Busy Beaver function
• Ackermann's Function
• LOOP programs
• and their capabilities

• WHILE programs
• UTM Theorem
• Normal Form Theorem
• SMN Theorem / Currying (Schönfinkeling)
• Recursion Theorem, Fixedpoint Theorem, QUINES
• Oracle WHILE Programs
• Arithmetic Hierarchy
• Post/Friedberg/Muchnik

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

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

• polynomial-time reductions
• equivalent problems Clique, Independent Set, Boolean Satisfiability, 3-Satisfiability
• Cook-Levin Theorem, Master Reduction

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

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

• (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.

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.