..
Suche
Hinweise zum Einsatz der Google Suche
Personensuchezur unisono Personensuche
Veranstaltungssuchezur unisono Veranstaltungssuche
Katalog plus

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

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