What is computation? Why are some problems harder than others?
These are the fundamental questions of the theory of computation. We will look at models of computation, decidable and undecidable problems, time complexity, NP-completeness, space complexity, the class PSPACE, randomness, and finally interaction and pseudorandomness. If things go well, I would like to cover the PCP Theorem in the course.
I will be following the book The Nature of Computation by Cristopher Moore and Stephan Mertens. The book is somewhat expensive (but it has nearly 1000 pages), and I do not require students to buy it. The book will be on course reserve in the library during the semester.
I hope we can cover (parts of) Chapters 7, 4, 5, 6, 8 during the semester.
Jiwon Park.
The class meets Wednesday and Friday from 10:30 to 11:45 in classroom 112 in building N1.
Attendance will be taken in nearly every class. If you miss at most 4 lectures, you receive 10 attendance points. For 5 missed lectures, you receive 9 attendance points, and so on. For 14 or more missed lectures you receive no attendance points.
Going to a conference, workshop, doctor, interview, is no excuse for missing the class — you can use the four free missed classes for this.
Lectures are given in English.
The final grade will be composed as follows (small changes reserved):
There will a midterm exam and a final exam.
The midterm exam takes place on October 22 in room 1101 in building E3-1, from 9:00 to 11:45.
The final exam takes place on December 12 from 9:30 to 12:00 in building E3-1, from 9:00 to 11:45.
We have a Glassboard forum for this course. The invitation code to enter the board will be provided in the first class.
I will post announcements and you can ask questions on the Glassboard. Both Korean and English are acceptable :-), but you make it easier for me if you write in English. It is okay to register on Glassboard with a nickname if it makes it easier for you to ask questions :-)
You are responsible for checking the announcements regularly. This is easier if you install the Glassboard app for iPhone or Android, as it will notify you when a posting appears on the board.
We will be following the book The Nature of Computation by Cristopher Moore and Stephan Mertens. The book is somewhat expensive (but it has nearly 1000 pages), and students are not required to buy it. The book is on course reserve in the library during the semester.
Other books about the theory of computation are:
The material covered in the lectures so far:
| 09-03 | No class (business trip) | |
| 09-05 | No class (business trip) | |
| 09-10 | Chuseok Holiday | |
| 09-12 | Introduction | slides, Book 7.1.1, 7.2.1 |
| 09-17 | More history, Halting problem | Book 7.1.2, 7.2.2 |
| 09-19 | Other undecidable problems, Gödel's incompleteness theorem | Book 7.2.5 |
| 09-24 | Primitive Recursive Functions, BLOOP, Ackermann is not prim. recursive | 7.3.1, 7.3.2 |
| 09-26 | Recursive Functions, FLOOP, Kleene normal form | 7.3.3, 7.3.4 |
| 10-01 | \(\lambda\)-calculus | 7.4 |
| 10-03 | Holiday | |
| 10-08 | \(\lambda\)-calculus is equivalent to partial recursive functions | 7.4.3, 7.4.4 |
| 10-10 | Turing machines and the Church-Turing thesis, counter machines | 7.5.1, 7.5.2, 7.6.1 |
| 10-15 | Undecidable problems: Fractran, Wang tiles, Piecewise linear functions | 7.6.2, 7.6.5, 7.6.6 |
| 10-17 | The class P and some problems in NP, reductions | 4.2.1, 4.2.2 |
| Midterm week (Midterm exam 10-22, 9:00~11:45 in 1101, E3-1 | ||
| 10-29 | P and NP, Reductions, SAT, 3Coloring to Planar3Coloring | 4.1, 4.2.1, 4.2.2, 4.2.4 |
| 10-31 | k-Coloring to k+1-Coloring, 3-SAT, k-SAT, NTIME, Nondeterminism | 4.3.1, 4.3.2, 4.3.3, 4.4.1 |
| 11-05 | NP-completeness, Domino, SAT | lecture notes (*) |
| 11-07 | NP-completeness of NAE-SAT, 3-Coloring, Independent Set and Max-2-SAT, Polynomial Hierarchy | 5.3.1, 5.3.2, 5.3.3, 6.1.1 |
| 11-12 | P = NP implies EXP=NEXP, Time hierarchy | 6.1.2, 6.3 |
| 11-14 | Relativized P and NP, Oracles, Problems in the Gap | 6.4, 6.6 |
| 11-19 | No class | |
| 11-21 | Space-complexity, L, PSPACE, NSPACE, NL, Reachability is in NL | 8.1, 8.2 |
| 11-26 | log-space reductions, Reachability is NL-complete, Savitch's theorem | 8.3, 8.4 |
| 11-28 | Immermann-Szelepcsényi Theorem, PSPACE as a game | 8.5, 8.6.1 |
| 12-03 | Two-Player-SAT, QSAT, Geography are PSPACE-complete | 8.6.2, 8.6.3, 8.7.1 |
| 12-05 | Arthur and Merlin, IP = PSPACE | 11.1.1, 11.2 |
| 12-10 | Probabilistically Checkable Proofs | 11.3.1 |
| 12-12 | Final exam 9:30~12:00 in 1101, E3-1 | |
(*) Extract from Introduction to Theory of Computation by Anil Maheshwari and Michiel Smid.
There will be several homework assignments. You will have about one week to complete the assignment. Homeworks can be turned in in either Korean or English, and must be submitted before noon (11:59 am) on the day of the deadline. This deadline is hard, because we will review the homework in the head-banging session on the same afternoon!
Please submit your homework in the homework box near the department office on the fourth floor of building N1.