Complexity Theory

Course Notes

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

Online Resources

• An alternative view of the travelling salesman problem.
• A short video giving highlights of complexity theory.
• Oded Goldreich. P, NP and NP-completeness. Cambridge University Press.
  Available here with full textbook access from within the University of Cambridge or through a University VPN.
• Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach.
  Available here in draft form.

Suggested exercises

• Supervision 1
     2020 Paper 6 Question 3 Parts (a) and (b).
     2020 Paper 6 Question 4 Parts (a), (b), and (c).
     2018 Paper 6 Question 3 Parts (a), (b), and (c).
     2014 Paper 6 Question 1 Parts (a) and (c).
     2012 Paper 6 Question 1.
• Supervision 2
     2019 Paper 6 Question 4.
     2017 Paper 6 Question 2.
     2015 Paper 6 Question 1.
     2014 Paper 6 Question 2.
     2011 Paper 6 Question 2.
• Supervision 3
     2018 Paper 6 Question 4.
     2016 Paper 6 Question 2.
     2014 Paper 6 Question 1 Part (b).
     2011 Paper 6 Question 1.
     2010 Paper 6 Question 2.