This course in Theory of Computation complements our courses on the design and analysis of algorithms: It explores the limits of what can be computed - and in particular which problems cannot be solved, neither efficiently nor at all: regardless of how smart an algorithm anyone is ever to invent! Such investigations give rise to a taxonomy of classes of computability and complexity, based on the important notion of completeness. This permits to judge whether a specific algorithm is optimal for some problem (and any attempts for further improvement thus bound to fail), or how far off from optimal it may be.
The course will take place in the first five weeks of the semester, from September 1 to October 1.
The class meets Monday, Wednesday, and Friday from 11:00 to 11:50 in room 2443 (class room 3) of the Computer Science Building (E3-1). Lectures are given in English.
Grading is based on homeworks (40%), a final exam (40%), and participation in class (20%).
There will be a final exam on October 13, from 11:00 to 12:30 in our usual classroom.
We will use these books as references. The first two should be available in the library, students do not need to buy them.
Here is a rough list of what we will cover in each week of the semester.
| Week 1 | Turing machines, diagonalization, uncomputability of the Halting problem |
| Week 2 | Higher degrees of uncomputability, Kleene's arithmetical hierarchy |
| Week 3 | Space hierarchy theorem, time hierarchy theorem |
| Week 4 | Relativizations of the P versus NP question |
| Week 5 | Solution to Post's Problem |
The material covered in the lectures so far:
| 09-01 | Introduction to Diagonalization and Computability | Slides |
| 09-03 | Diagonal Language, Halting Problem, Undecidability | Slides |
| 09-05 | Rice's Theorem, Oracle Computation | Slides |
| 09-08 | Discussion of Homework 1 | |
| 09-10 | Arithmetical Hierarchy | Slides |
| 09-12 | Time Hierarchy Theorem | Slides |
| 09-15 | Chuseok Holiday | |
| 09-17 | Discussion of Homework 2 | |
| 09-19 | Relativizations of "P versus NP" | Slides |
| 09-22 | Discussion of Homework 3, Degrees of Undecidability | Slides |
| 09-24 | Discussion of Bonus Exercise, Post's Problem | Slides |
| 09-26 | Finite Injury Priority Diagonalization | Slides |
| 09-29 | Discussion of Homework 4 | |
| 10-01 | Quine's theorem, Bonus material | Slides |
| 10-13 | Final exam (11:00 to 12:30) | |
There will be one homework assignment per week, and you will have one week to complete an assignment. Programming homeworks are submitted by email to the instructor, theoretical homeworks must be submitted on paper and should be handed in at the beginning of class.
We have a bulletin board for announcements and discussions. You can also post your questions there. Both Korean and English are acceptable on the BBS :-)