Complexity

---

BA in Computer Science BA in Mathematics & Computer Science MSc in Mathematics and Foundations of Computer Science MSc in Computer Science, Schedule B

16 lectures MT Dr Stephan Kreutzer

---

Overview

This course is an introduction to the theory of computational complexity and standard complexity classes. One of the most important insights to have emerged from Theoretical Computer Science is that computational problems can be classified according to how difficult they are to solve. This classification has shown that many computational problems are impossible to solve, and many more are impractical to solve in a reasonable amount of time. To classify problems in this way, one needs a rigorous model of computation, and a means of comparing problems of different kinds. This course introduces these ideas, and shows how they can be used.

Learning Outcomes

The course is designed to enable students to:

1. State precisely what it means for a problem to be computable, and show that some problems are not computable.
2. State precisely what it means to reduce one problem to another, and construct reductions for simple examples.
3. Classify problems into appropriate complexity classes, including P, NP and PSPACE, and use this information effectively.

---