Department of Computer Science and Technology

Complexity Theory

Course Notes
and
Slides

Suggested Exercises
Note: these exercises are intended to explore in further detail some issues raised in the lectures, and encourage you to extend further the techniques that have been developed there. They are not intended to reflect the kind of questions that might come up in an exam. Please have a look at past exam papers for an idea of what kinds of questions might be asked. Also, it is not intended that each of the exercise sheets can be covered in a single supervision. Supervisors may (if they wish) select from these exercises ones suitable for setting as supervision work.

Exercise Sheet 1
Exercise Sheet 2
Exercise Sheet 3