Complexity Theory

• Course codes: B-GeA-12→KTH12 ·M-KLOG-12-K→KTH12
• External links: qis

Overview

Description

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.

Time and Place

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

Grading

• There will be 3-4 mandatory written assignments; you can solve them in teams of size 2.
• The written exam will take place on Tuesday, July 19 at 10-13 in H10.

Week plan

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

1. ✓ 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)

2. ✓ NP and NP completeness [AB ch. 2.1-2.3, 2.5-2.7]
   Homework: 2.10, 2.8, 2.25, 2.29, 2.6b*, 2.30*

3. ✓ Diagonalization [AB, ch. 3]
   Homework: 3.5, 3.6, 3.7*, 3.8*

4. ✓ Space complexity [AB, ch. 4]
   Homework: 4.1, 4.2, 4.3, 4.7
   Written assignment: pdf

5. ✓ The polynomial hierarchy and alternations [AB, ch.5]
   Homework: 5.3, 5.7, 5.10, 5.13

6. ✓ Boolean circuits [AB, ch. 6]
   Homework: 6.3, 6.8, 6.9*, 6.12

7. ✓ Randomized computation [AB, ch.7]
   Homework: 7.4, 7.7, 7.9
   Written assignment: pdf. Please consider handing in the assignment as a team of size 2.

8. ✓ Interactive proofs [AB, ch. 8.1-8.3]
   Homework: 8.1, 8.2, 8.6*

9. ✓ PCP Theorem [AB, ch. 11]
   Homework: Read!, 11.2, 11.3, 11.6, 11.9*, 11.15

10. ✓ Decision Trees [AB, ch. 12]
    Homework: 12.1, 12.2, 12.3, 12.6

11. ✓ Complexity of Counting [AB, ch. 17] (this week happening via Zoom!)
    Homework: 17.2, 17.4, 17.6*

12. ✓ Self-study: Third and final written assignment: pdf. Please consider handing in the assignment as a team of size 2.

13. ✓ ⊕ ∉ AC0 [AB, ch. 14.1]

14. ✓ Recap

Prerequisites

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.

Contents

• 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.

Literature

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.

Further resources

• Similar Courses:
  • 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.
• Also see TCS @ Princeton.