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
TA: 이현우 (head)
Language: English only
Grading: Homework 30%, Quiz 10%, Midterm exam 30%, Final exam 30%
Synopsis/Syllabus:
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
II. Advanced Computability (ppt, pdf):
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
Example problems: Euler/Hamiltonian Circuit, Edge/Vertex Cover
Boolean formulas and Satisfiability
nondeterministic WHILE+ programs
Time Hierarchy Theorem: P≠EXP
IV. Structural Complexity / NPc (ppt, pdf):
polynomial-time reduction
equivalent problems: Clique = Independent Set ⇐ Boolean Satisfiability ⇐ 3-Satisfiability ⇐ Independent Set
Cook-Levin Theorem, Master Reduction
Bin Packing is NP-complete
Scenarios for P/NP, Ladner's Theorem
V. PSPACE and Polynomial Hierarchy (ppt, pdf):
PSPACE and QBF
Master Reduction
A PSPACE-complete Two-Player Game on Digraphs
Savitch's Theorem: NSPACE(f) in SPACE(f²)
Immerman-Szelepcsényi: NSPACE(f) = coNSPACE(f)
Oracle Complexity and Polynomial Hierarchy, Semantically and Syntactically
Limitations of Relativizing Proofs: Baker, Gill & Solovay; Bennett & Gill
VI. Perspectives (ppt, pdf):
complexity of cryptography: UP and one-way functions
counting problems: #P and Toda's Theorem
Approximation algorithms and hardness
randomized algorithms, probability amplification, BPP, Adleman and Sipser-Gacs-Lautemann Theorems
fixed-parameter tractability and hardness
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.
Academic Honesty
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.
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).
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.
E-Learning
Instead please use the KLMS Bulletin Board or visit the TAs during their office hours.