Vorlesung Komplexitätstheorie I (WS 2021/2022)

 

Organisatorisches

• Veranstalter: Prof. Dr. Markus Lohrey (Raum H-A 7109, Tel. 0271-740-2826)
• Übungsleiterin: Louisa Seelbach (Raum H-A 7104)
• Vorlesungstermine:
  • Donnerstag 10:00-12:00 in H-B 4419/20
• Übungen:
  • Donnerstag 12:00-14:00 in H-B 4419/20
  • Die erste Übung findet am 21.10.2021 statt.

 

Einige Themen

• Zeit- und Platzkomplexitätsklassen
• Hierarchiesätze
• Reduktionen
• Komplementabschluss nichtdeterministischer Platzklassen (Satz von Immerman, Szelepcsenyi)
• Vollständige Probleme für P, NP, PSPACE

 

Folien

Beispiel zur Reduktion von 3SAT auf Hamilton-Kreis (der gezeigte Hamilton-Kreis entspricht der Belegung x1 = 1, x2 = 0, x3 = 1).

 

Übungsblätter

• Blatt 1
• Blatt 2
• Blatt 3
• Blatt 4
• Blatt 5
• Blatt 6

Lehrbücher

• 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