Content

Here is a selection of topics we plan to cover in the lecture:

• How do we model computation, how do we measure time/space usage, and why the details do not matter (much)
• Polynomial-time computation (P, NP, coNP)
• NP-completeness: what it is, why it matters, how to prove it, some typical NP-complete problems (SAT, 3-SAT, Karp's problems)
• Space complexity and Savitch's theorem
• Beyond NP: PSPACE, the Polynomial Hierarchy, alternation
• Logarithmic space classes (L and NL)
• Time and space hierarchy theorems
• Selected advanced topics subject to how much time we have (circuit complexity, oracles and relativisation, probabilistic classes, interactive proofs, approximation hardness)

Prerequisites

You must have passed the exams for Introduction to Theoretical Computer Science (ETI) and Discrete Structures. Note that Complexity Theory is a very theoretical and mathematical course, so if you hated these two courses, you will probably not enjoy this one either. Conversely, if you enjoyed these courses (especially ETI) and want to learn more, this course may be right for you.

Having attended the Logic helps since we will build on some of the material covered there, but you should be fine even if you have not done that one yet.

More abstractly, the following skills are helpful:

• Being comfortable with formal mathematical notation, mathematical thinking, etc.
• Good familiarity with basic discrete mathematics (knows what a relation is, what a graph colouring is, etc.)
• Familiarity with propositional and first-order logic (understand what satisfiability is, not scared of quantifiers, etc.)
• Turing machines
• Some knowledge of formal languages, automata, grammars, and regular expressions is useful but not required.

Recommended literature

The lecture is roughly based on the two books below. Many more books on Complexity Theory exist. Most of these are, in my opinion, more demanding and tougher reads. Arora/Barak and Sipser strike a good balance between rigour, the breadth and depth of the material they present, and accessibility. Since this is what I aim for in my course as well, I think those books are a good match.

In any case, all the concepts we will talk about are very standard, so if you ever feel that you need more detailed explanations you can easily find a lot of additional material online.

M. Sipser, Introduction to the Theory of Computation, 2014.
A nice and simple introduction to the basics of complexity theory (and much more).

S. Arora & B. Barak, Computational Complexity: A Modern Approach, 2007.
Much more detailed than Sipser. Caution: The draft version you can find on the internet contains numerous mistakes!

D. C. Kozen, Theory of Computation, 2006

Additional recommended material

Note again that this course is a very theoretical one. Being comfortable with mathematical reasoning and thinking is an absolute must. If you find that you still struggle with this, the following book may be a good resource:

D. J. Velleman, How to Prove It: A Structured Approach, 2006.