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:

• 1. Vorlesungswoche: VL 1 (mit allgemeinen Hinweisen), danach folgen wir weitgehend dem Foliensatz von Herrn Müller, siehe stud.ip  (oder persönliche Nachfrage)
  
  
• 8. Vorlesungswoche: Zusatzmaterialien aus Newcastle: Complexity, Reductions, NP-Completeness, Artikel aus EATCS Bulletin, siehe auch Publikationsliste