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 it does not matter (much)
- Polynomial-time computation (P, NP, coNP)
- NP-completeness: what it is, 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
- Time and space hierarchy theorems
- Logarithmic space classes (L and NL)
- Selected advanced topics subject to how much time we have (circuit complexity, oracles and relativisation, probabilistic classes, interactive proofs)
Prerequisites
Concretely, in terms of lectures: Having passed the courses Introduction to Theoretical Computer Science (ETI) and Discrete Structures. Note again that this is a very theoretical and mathematical course, so if you hated these two courses, you may 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 will be somewhat helpful since we will build on some of the material covered there, but you should be fine even if you have not attended that one yet.
More abstractly:- Generally: 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 could be useful but is 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 especially Sipser strike a good balance between the breadth and depth of the material they present and accessibility. 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.
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.