Vorlesung Strukturelle Komplexitätstheorie (WS 2020/21)

Aktuelles

Momentan planen wir, die Veranstaltung noch in Präsenz durchzuführen. Dies kann sich jedoch auf Grund der aktuellen Situation noch ändern.
Die Übungen beginnen am 3.11.

Organisatorisches

Veranstalter: Prof. Dr. Markus Lohrey (Raum H-A 7109, Tel. 0271-740-2826)
Übungsleiter: Michael Figelius (Raum H-A 7104, Tel. 0271-740-3415)
Termine: Mittwoch, 10:15-11:45, und Donnerstag, 14:15-15:45, via Zoom
Termin Übung: Dienstag, 12:00-14:00, in H-C 3309; ab dem 1.12.2020 via Zoom

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

Folien

Videos

Übungsblätter

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

Aktualisiert via XIMS am 10.2.2021 von C. P. Reh