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
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.
Homework should be turned in on time, before 9:10. Otherwise, it will be considered late. Homework can be written in Chinese or English. If you have to use emails to turn in the homework, please use the PDF format with your student ID number as the file name and send it using your NTU or NTUCSIE email account. Time stamp will be used to determine if the homework is late or not. Beware of the potential email reliability problem. You are expected to finish your own homework on your own. Do not copy or collaborate with fellow students. Never give your homework to other students or publish your homework because it may be copied and you in turn may be suspected of copying other's homework!
If you prefer, you may submit your homework solutions via the CEIBA system before the stated deadlines. Name your file StudentID_HW_# for easy reference. Example: R91723054_HW_2.pdf.
The major results covered in the course, time permitting, are listed below
for your reference.