Vorlesung Komplexitätstheorie (WS 2018/19)

Informationen

• Die Vorlesung findet im Raum H-A 7101 statt. 
• Die Vorlesung am 22.11.2018 entfällt. Dafür findet die Übung bereits um 12:15 statt. Die Übung am 29.11.2018 entfällt.
• Die Vorlesung am 20.12.2018 entfällt. Dafür findet die Übung bereits um 12:15 statt. Die Übung am 10.01.2019 entfällt.

 

Organisatorisches

• Veranstalter: Danny Hucke (Raum H-A 7104, Tel. 0271-740-3415)
• Übungsleiter: Carl Philipp Reh (Raum H-A 7105, Tel. 0271-740-3233)
• Termine Vorlesung:
  • Donnerstag, 12:00-14:00, im H-F 115 H-A 7101
  • Donnerstag, 14:00-16:00, im H-F 115 H-A 7101
• Termin Übung: Donnerstag, 16:00-18:00, im H-F 115

---

Die Komplexitätstheorie beschäftigt sich mit der für die Lösung algorithmischer Fragestellungen notwendigen Rechenzeit und Speicherplatz. Insbesondere sollen Techniken entwickelt werden, mittels derer sich beweisen lässt, dass die Lösung gewisser Probleme schwierig (d.h. viel Speicher oder eine hohe Laufzeit benötigt). Die Vorlesung soll die zentralen Konzepte der Komplexitätstheorie vermitteln.

Einige Themen

• Zeit- und Platzkomplexitätsklassen
• Hierarchiesätze
• Reduktionen
• Komplementabschluss nichtdeterministischer Platzklassen (Satz von Immerman, Szelepcsenyi)
• Vollständige Probleme für P, NP, PSPACE
• Orakel-Turingmaschinen
• Alternierende Maschinen
• Schaltkreiskomplexität
• Interaktive Beweissysteme

---

Erster Teil der Folien (klassische Komplexitätstheorie) (07.12.2018) 

Zweiter Teil der Folien (Kommunikationskomplexität) (24.01.2019)

Übungsblätter 

• Blatt 1
• Blatt 2
• Blatt 3
• Blatt 4
• Blatt 5
• Blatt 6
• Blatt 7
• Blatt 8
• Blatt 9
• Blatt 10
• Blatt 11

 

---

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

---

Impressum