Table of Contents

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.

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

II. Advanced Computability (ppt, pdf):

III. Computational Complexity (ppt, pdf):

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

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

VI. Perspectives (ppt, pdf):

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

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.