Complexity Theory

University of Cambridge Computer Laboratory

Principal lecturer: Dr Anuj Dawar
Taken by: Part IB, Part II(General) Diploma



Slides for the lectures:
Corrections to the notes handed out at the beginning of the course are given in the errata sheet, last updated on 17 May, 2000.
The extra slides used on 12 May on the Circuit Value Problem, are here.
Suggested Exercises
Exercise Sheet 1 (4 May 2000)
Erratum: In Question 2 of sheet 1, in order to show that f(g) is constructible, you need to assume that f(n) > n.

Exercise Sheet 2 (9 May 2000)

Exercise Sheet 3 (15 May 2000)

Erratum: In Question 3 of sheet 3, the definition of a Horn clause should require at most one positive literal per clause, rather than exactly one.

Exercise Sheet 4 (22 May 2000)

Errata: In Question 2 of sheet 4, for "exactly one triple", read "exactly one quadruple".

In Question 4, part (b), for "reducible" read "linear time reducible".

Past Exam Questions
As the syllabus for the course has changed this year from what it was in earlier years, some questions from previous exams may not be relevant. However, if you have mastered the material taught this year, you should be able to attempt the following questions from past exams:

IB | II(General) | Diploma

Provisional information only