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.
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]
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.
AB: Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak.
[Volltext als E-Book].