Theory of Computation (CS422) in Fall 2017
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 #2112 in building E3
Schedule: Wednesdays and Fridays 9:00am to 10:15am
Language: English only
Teaching Assistant: Ivan Koswara
Office/claiming hour: Fridays 10:30am to 11:30am in E3 #3409
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 (Monday, Oct 16, 9h00-11h30, #2112)
and a final exam (Monday, Dec 11, 9h00-11h30, #2112).
We make a special pedagogical effort
to avoid the arduous Turing machine formalism
and instead employ a variant of WHILE programs.
- Motivating Examples:
- comparison-based sorting
- finite automata
- asymptotic cost
- addition chain
- matrix multiplication
- diagonalization / undecidable Halting Problem
- Basic Computability Theory
Un-/Semi-Decidability and Enumerability
Reduction, degrees of undecidabiliy
(Busy Beaver function)
and their capabilities
- Advanced Computability
Normal Form Theorem
SMN Theorem / Currying (Schönfinkeling)
Recursion Theorem, Fixedpoint Theorem, QUINES
(Post's Correspondence Problem, truth of arithmetic formulae)
Model of computation with (bit) cost: WHILE+
P, NP, PSPACE, EXP
and their inclusion relations
nondeterministic WHILE+ programs
Integer Linear Programming
Structural Complexity / NPc
Clique, Independent Set, Boolean Satisfiability,
Cook-Levin Theorem, Master Reduction
Ladner's Theorem (without proof)
PSPACE and Polynomial Hierarchy
QBF, 3QBF, GRAPH
- Advanced Complexity
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.
Late homework submissions will be ignored
(for grading: you could still
Copied homework solutions receive 0 points.
Cheating during the exam results in expulsion and 0 points.
Students are required to submit the
declaration of Academic Honour Code
with their signature
in the lecture on Friday, September 8 at 9am.
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.
- 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).
- KAIST Learning Management System
- slides for
- slides for the lecture on 09/15
- homework assignments
#1 due Sep 7,
#2 due Sep 22,
#3 due Oct 13,
#4 due Nov 03,
#5 due Nov 17 by email,
#5 due Dec 01.