COMS 30126: Computational Complexity Theory

Course materials

LECTURE NOTES are available here: LECTURENOTES.pdf
New version of notes 16 April 2009. Includes new section: Interactive proof systems and the class IP.

Additional INSERTS for lecture notes are available here: INSERTS.pdf
(This is a scanned file of size 12.4MB)

PROBLEM SHEETS are available here:
sheet1.pdf
sheet2.pdf
sheet3.pdf
sheet4.pdf
sheet5.pdf
sheet6.pdf

SOLUTIONS TO PROBLEM SHEETS will become available here as the course progresses. (These are scanned files of the indicated sizes)
sheet1solutions.pdf (1.96MB)
sheet2solutions.pdf (1.42MB)
sheet3solutions.pdf (2.21MB)
sheet4solutions.pdf (3.24MB)
sheet5solutions.pdf (1.21MB)
sheet6solutions.pdf (124KB)

COURSEWORK will become available here: coursework.pdf

GUIDE TO EXAMINABLE MATERIAL will become available here: examguide.pdf


THE P vs. NP QUESTION -- some further references!
If you wish to learn more about the P vs. NP question, here are two interesting papers:

"The history and status of the P versus NP question", by M. Sipser (Proc. of 24th annual ACM Symopsium on the Theory of Computing, p603-18 (1992))
available here: PvsNPhistory.pdf

"Guest column: "The P =? NP Poll", by William Gasarch (SIGACT News vol 33, p34-47 (June 2002))
available here: PvsNPpoll.pdf
This reports the results of a poll, asking many leading theoretical computer scientists their opinion on when and how the P vs. NP question will be resolved.