University Homepage School Homepage School Contacts School Search

Computational Complexity (INF-4-CMC)

This course is offered in the second semester, on Mondays and Thursdays at 15:00. For the 2012-13 year, lectures are in the Robson Building Lecture Theatre. The course is taught by Rahul Santhanam. Note that the first lecture for the 2013 instalment will be on Thursday, 16 January.

• Learning resources
  • Course Notes
    • Lecture Notes Part 1.
    • Lecture Notes Part 2.
    • Lecture Notes Part 3.
    • Lecture Notes Part 4
    • Lecture Notes Part 5
    • Lecture Notes Part 6
    • Supplementary Note 1: Proof of the Hennie-Stearns theorem.
    • Supplementary Note 2: Proof of the Immerman-Szelepcsenyi theorem
  • Old Course Notes
    • Chapter 1. Turing machines and complexity classes.
    • Chapter 2. Natural classes and completeness.
    • Chapter 3. Circuits and parallel computation.
    • Chapter 4. An introduction to randomised computation.
    • Chapter 5. Provably intractable problems.
  • Revision Guide
  • The world's original and first Complexity Blog (Lance Fortnow).

• Coursework
  • Exercise Sheet 1 (due February 15) (Solutions)
  • Exercise Sheet 2 (due Mar 15) (Solutions)
  • Exercise Sheet 3 (due Apr 5) (Solutions)

• Feedback: please fill in a questionnaire!

• Past Examination Papers
  • April 1996
  • April 1997
  • May 1998
  • April 1999
  • May 2000
  • April 2001
  • April 2002 (with solutions to Q1, Q2 and Q3).
  • April 2003 (with solutions to Q1, Q2 and Q3).
  • April 2004 (or with solutions).
  • May 2005 (and solutions).