skip to primary navigationskip to content

Department of Computer Science and Technology

Complexity Theory

Course pages 2020–21

Complexity Theory

Course Notes


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