Theory of Computation (CS422/MAS480B)

Fall Semester 2014

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.

Course information

Otfried Cheong Office: E3-1 3434, Phone: 3542.
Teaching assistant

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.

Grading policy

The final grade will be composed as follows (small changes reserved):

  • Homework (20%), Midterm exam (30%), Final exam (40%), Participation (10%).

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.

Bulletin board

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.

Text book, lecture notes, slides

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:

  • I may use one chapter of the free textbook Introduction to Theory of Computation by Anil Maheshwari and Michiel Smid. You can download the PDF file of the book here.
  • Introduction to the Theory of Computation, Michael Sipser, Second International Edition, Course Technology 2006.
    Check out its errata page, which contains a few substantive (as opposed to stylistic) errors.
  • Elements of the Theory of Computation (2nd. ed.); Harry R. Lewis, Christos H. Papadimitriou, Prentice-Hall, August 1997.
  • Computational Complexity: A Modern Approach; Sanjeev Arora and Boaz Barak, Cambridge University Press 2009.

Course progress

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.