Computing Theory Course

Computing Theory

Time: 9:10--12:00 Wednesday



If IP=PSPACE, then TCP=NP.
---Class of 2000, M.S. (overheard)

A professor always included this question on his final exams:
"What did you think of this course?"
He discontinued the practice after receiving this response:
"This was the most complete course I ever took.
Anything we didn't go over during class
was covered in the final exam."
---Adapted from Reader's Digest

Two hunters are being pursued by a bear;
one stops to change into his running shoes.
The other tells him he is crazy: there is no
way he can run faster than a bear.
``I don't have to run faster than a bear,''
replies the first. ``I only have to run faster than you.''
The Economist, 18 March 2002



To the students,

This course emphasizes computational complexity and its applications. We will go over, in my opinion, the most interesting and/or important results in the field. You are expected to read the textbook for any background knowledge not covered in the lectures if your undergraduate education has not prepared you for this course. The textbook will, in general, be followed.

The mathematical techniques used in this course are wide-ranging but accessible. Undergraduate discrete mathematics course should be more than adequate. Math majors should be prepared to find standard mathematics used in unexpected ways. Combinatorics, probability, graph theory, number theory, and, to a less extent, group theory are the principal analytical tools. We shall skip predicate logic (Frege 1879) and the associated profound results of completeness and incompleteness (Godel 1930, 1931).

I hope you will be rewarded with the insights, sense of beauty, and applications that some of the results convey. There is also the satisfaction that, unlike many other fields in computer science (including those taught by me), many of the topics will still be taught to students decades from now.


Notes [ 2001, 2002, 2003 ]


Examinations and grading

  1. There was a mid-term exam on November 10, 2004 (closed book).
    • The examination will cover the lecture notes up to p. 251 given on October 20, 2004 (roughly Chapters 1 through 8 of the textbook, excluding Chapters 5 and 6).
    • The use of electromagnetic devices to transmit or receive signals during the examination will guarantee eviction from the class.
    • Bring your student photo ID for possible spot checks.
    • Students with an odd-numbered student ID take the test during 9:20--10:30. You shall not leave the room before 10:40.
    • Students with an even-numbered student ID take the test during 10:50--12:00.
    • Answers (prepared by the TA)
  2. There will be a final exam on January 12, 2005 (closed book).
    • The examination will cover the lecture notes from p. 251 (October 20, 2004) up to p. 559.
    • The use of electromagnetic devices to transmit or receive signals during the examination will guarantee eviction from the class.
    • Bring your student photo ID for possible spot checks.
    • Students with an even-numbered student ID take the test during 9:20--10:30. You shall not leave the room before 10:40.
    • Students with an odd-numbered student ID take the test during 10:50--12:00.
    • Answers (prepared by the TA)
  3. Your grades will be based on the grades of the exams.

The major results covered in the course, time permitting, are listed below for your reference.