Lecture Complexity Theory I (WS 2022/2023)
Organisation
- Lecturer: Prof. Dr. Markus Lohrey (room H-A 7103, phone 0271-740-2826)
- Tutor: Louisa Seelbach (room H-A 7104)
-
Dates:
- Thursday 10:00-12:00 in H-B 6414
-
Tutorial:
- Friday 8:00-10:00 in H-B 6414 (every second week)
- The first tutorial will be on October 21.
Topics
- Time and space complexity classes
- Space and time hierarchy theorems
- Reductions
- Complement closure of nondeterministic space classes (Theorem of Immerman, Szelepcsenyi)
- Complete problems for P, NP, PSPACE
German version of the slides
English version of the slides
Example for the reduction from 3SAT to Hamilton circuit (the shown Hamilton circuit corresponds to the truth values x1 = 1, x2 = 0, x3 = 1).
Exercise sheets
- Blatt 1 (Exercise 1)
- Blatt 2 (Exercise 2)
- Blatt 3 (Exercise 3)
- Blatt 4 (Exercise 4)
- Blatt 5 (Exercise 5)
- Blatt 6 (Exercise 6) (next tutorial: February 3, 2023)
Literature
- Sanjeev Arora und Boaz Barak: Complexity Theory: A Modern Approach. Cambridge University Press 2009
- Christo H. Papadimitriou: Computational complexity. Addison-Wesley 2005
- Ingo Wegener: Komplexitätstheorie. Grenzen der Effizienz von Algorithmen. Springer 2003