Komplexitätstheorie

Prof. Dr. Henning Fernau

Vorlesung im Hauptstudium über 2 SWS mit Übungen über 2 SWS

Die Komplexitätstheorie ist neben den Formalen Sprachen eine der klassischen Säulen der Theoretischen Informatik. Behandelt werden u. a. die Berechnungsressourcen Zeit und Speicherplatz, verschiedene Komplexitätsklassen wie L, NL, P, NP, PSPACE, die Klassifikation konkreter Probleme, Reduzierbarkeit und Vollständigkeit, harte Probleme der obigen Komplexitätsklassen sowie Hierarchiesätze.

VL (Beginn erste Vorlesungswoche) dienstags 14 - 16 Uhr F 55

<link internal-link>Übungen (Raible; Beginn dritte Vorlesungswoche): mittwochs 8 - 10 Uhr H 11

Folien: