Complexity Theory is a beautiful field that studies different models of computation as well as their relationships to each other. The most famous open problem in this field is the P vs. NP problem. In this course, you will discover elegant proof techniques, fascinating ideas, and exciting open questions.

**Lectures.**Tue 12-14, Wed 10-12 in H9.**Tutorials.**Tue 10-12 in H9.

- There will be 3-4 mandatory written assignments; you can solve them in teams of size 2.
- Depending on class size, the exam will be oral (35 minutes) or written (180 minutes).
- In addition, there will be ungraded in-class and homework exercises.

The summer term has 14 weeks, the following is a preliminary plan:

✓

**Introduction: Efficient universal Turing machine.**[AB 1.2-1.4, 1.6-1.7]

In-class exercises: Example 1.1, Claims 1.5 and 1.6.

Homework: Exercises 1.5, 1.6*, 1.9, 1.10, 1.15. (* = hard, but well worth the effort)✓

**NP and NP completeness**[AB 2.1-2.3, 2.5-2.7]

Homework: 2.10, 2.8, 2.25, 2.29, 2.6b*, 2.30*✓

**Diagonalization**[AB, ch.3]

Homework: 3.5, 3.6, 3.7*, 3.8*✓

**Space complexity**[AB, ch.4]

Homework: 4.1, 4.2, 4.3, 4.7

Written assignment: pdf✓

**The polynomial hierarchy and alternations**[AB, ch.5]

Homework: 5.3, 5.7, 5.10, 5.13**Boolean circuits**[AB, ch.6]

Homework: 6.3, 6.8, 6.9*, 6.12**Randomized computation**[AB, ch.7]**Interactive proofs**[AB, ch.8]**PCP Theorem**[AB, ch.11]**Decision Trees**[AB, ch.12]**Complexity of Counting**[AB, ch.17]**Circuit Lower Bounds**[AB, ch.14]**NEXP ⊈ ACC0**[AB, addendum · paper]

This course is available for Bachelor *and* Master students!
You must have mastered Algorithms and Data Structures 1 and 2 (or equivalent) and you must love mathematics.

- Complexity classes: Log-space, NP, BPP, polynomial-time hierarchy, ACC0, EXP, NEXP, NP/poly, #P, etc.
- Karp-Lipton’s Theorem, Hardness vs. Randomness, NEXP ⊈ ACC0, PCP theorem, etc.

**AB**: *Computational Complexity: A Modern Approach* by Sanjeev Arora and Boaz Barak.

[Volltext als E-Book].

There is also a pdf on the book website, but be aware that it is not a final draft and has different chapter numbers.

- Dieter van Melkebeek’s Complexity Theory at UW Madison.
- Ryan Williams’ Automata, Computability, and Complexity Theory and Advanced Complexity Theory at MIT.

- For background reading on Turing machines, see:
- video lecture on chapter 6 in Jeff Erickson’s Models of Computation course.
- video lectures in Michael Sipser’s course at MIT.

- See TCS @ Princeton.