Lecture Complexity Theory I (WS 2023/2024)
Organisation
- Lecturer: Prof. Dr. Markus Lohrey (room H-A 7103, phone 0271-740-2826)
- Tutor: Julio Xochitemol (room H-A 7104)
-
Dates:
- Thursday 10:15-11:45 in H-B 6414
-
Tutorial:
- Friday 8:15-09:45 in H-B 6414 (every even week)
- The first tutorial will be on October 20.
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
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