Theory of Computation (CS422) in Fall 2023 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 (use only this email address!)
• TAs: Hakyeong Kim and Abbas Mammadov (use only this email address!)
• Schedule: Tuesdays and Thursdays, 10:30~12:00
• Location: E3-1 #1101 and online/Zoom
• Language: English only
• Grading: Attendance/Quiz 40%, Homework 20%, Midterm exam 20%, Final exam 20%
• Midterm: October 19, 9:00~11:45
• Final Exam: December 14, 9:00~11:45
• Prerequisites: CS300 Introduction to Algorithms, CS204 Discrete Mathematics

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 in/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

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.

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

• YouTube
• WHILE program simulator
• KLMS
• Due to the large number of students enrolled, we unfortunately cannot answer questions by email.
  

Instead please use the KLMS Bulletin Board or visit the TAs during their office hours.