Lecture Complexity Theory I (WS 2025/2026)

 

Organisation

• Lecturer: Prof. Dr. Markus Lohrey (room H-A 7103, phone 0271-740-2826)
• Tutor: Julio Xochitemol (room H-A 7105)
• Dates:
  • Thursday 10:15-11:45 in H-C 7326
• Tutorial:
  • Friday 8:15-09:45 in H-B 6414 (every odd week)
  • The first tutorial will be on October 24.

 

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

 

Material for the lectures

• German version of the slides (will not be updated anymore)
• English version of the slides
• Example for the reduction from 3SAT to Hamilton circuit

 

Exercise sheets

• Exercise 1

 

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