COMS 30126: Computational Complexity Theory
| Lecturer: | Markus Jalsenius |
| Unit director: | Raphaël Clifford |
Course materials
| Lecture notes (new 2011 version): | Lecture-notes-2011.pdf |
| Additional inserts for lecture notes: | Inserts.pdf (scanned file of size 12.4 MB) |
| Exercise sheets:
Solutions will become available as the course progresses. (These are scanned files of the indicated sizes.) |
Exercises-1.pdf Solutions-1.pdf (1.96 MB) Exercises-2.pdf Solutions-2.pdf (1.42 MB) Exercises-3.pdf Solutions-3.pdf (2.21 MB) Exercises-4.pdf Solutions-4.pdf (3.24 MB) Exercises-5.pdf Solutions-5.pdf (1.21 MB) Exercises-6.pdf Solutions-6.pdf (0.12 MB) |
| Coursework (due on 3 May 2011): | Coursework.pdf |
| Guide to examinable material: | 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 (Proceedings of the 24th Annual
ACM Symopsium on the Theory of Computing, p603–618, 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.