Course pages 2019–20

# Complexity Theory

**Slides**

- Lecture 1
- Lecture 2
- Lecture 3
- Lecture 4
- Lecture 5
- Lecture 6
- Lecture 7
- Lecture 8
- Lecture 9
- Lecture 10
- Lecture 11
- Lecture 12

**Video Lectures**

- Lecture 1
- Part 1 (17 minutes)
- Part 2 (30 minutes)
- And, an alternative view of the travelling salesman problem. (2 minutes)

- Lecture 2
- Lecture 3
- Lecture 4
- Lecture 5
- Lecture 6
- Lecture 7
- Lecture 8
- Lecture 9
- Lecture 10
- Lectures 11 and 12
- Part 1 (26 minutes)
- Part 2 (15 minutes)
- Part 3 (24 minutes)
- Part 4 (28 minutes)
- And, finally a short video that gives some of the highlights of complexity theory (10 minutes)

**Useful Online Resources**

- Oded Goldreich.
*P, NP and NP-completeness*. Cambridge University Press.

This is available here: here. When accessing from within the University of Cambridge, or through a University VPN, you should have access to the full textbook. - Sanjeev Arora and Boaz Barak.
*Computational Complexity - A Modern Approach*.

This is freely available online (in draft form) here.

**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.