en | de

Introduction to Complexity Theory

bachelor program

VU 3  SS 2024  703145

Content

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

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:

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.