Komplexitätstheorie

Ein Teilgebiet der (Theoretischen) Informatik beschäftigt sich mit der Frage, welche Probleme sich prinzipiell algorithmisch lösen lassen. Solche Probleme werden als berechenbar bezeichnet. Die Berechenbarkeitstheorie untersucht diese und verwandte Fragestellungen.

Eine wichtige Teilklasse der berechenbaren Probleme stellt die Klasse der entscheidbaren Probleme dar. Im Unterschied zum allgemeinen berechenbaren Problem gibt es zu jedem entscheidbaren Problem einen Algorithmus, der zu jeder Eingabe eine korrekte Antwort liefert. Der Algorithmus terminiert also stets. Da es sich damit um endliche Berechnungen handelt, kann für jede solche Berechnung ein sogenannter Ressourcenverbrauch bestimmt werden. Typische Ressourcen sind Laufzeit und Speicherplatzbedarf.

Die Komplexitätstheorie baut auf dieser Grundlage auf. Es werden entscheidbare Probleme anhand ihres Ressourcenverbrauchs klassifiziert, und entsprechende Problemklassen werden untersucht. Bekannte Klassen, Komplexitätsklassen, sind P und NP, die die Probleme umfassen, die sich in Polynomialzeit deterministisch entscheiden beziehungsweise nichtdeterministisch akzeptieren lassen.

Vorlesungsinhalt

Wir werden verschiedene Komplexitätsklassen eingeführen und untersuchen. Bekannteste und bedeutende Klassen sind L, NL, P, NP, PSPACE. Die Bedeutung dieser Komplexitätsklassen rührt unter anderem daher, daß sie eine Großzahl praktisch relevanter Probleme charakterisieren.

Höhepunkte der Vorlesung werden sein:

  • Existenz schwierigster Problem in einzelnen Komplexitätsklassen
  • Existenz unendlicher Hierarchien schwieriger Probleme
  • die Polynomialzeit-Hierarchie
  • Äquivalenz von deterministischem und nichtdeterministischem polynomiellem Raum (Satz von Savitch)
  • Komplementabschluß nichtdeterministischer Raumklassen (Satz von Immerman-Szelepcsény).

Voraussetzungen

Als grundlegendes Berechnungsmodell werden wir die Turing-Maschine verwenden. Kenntnisse aus der Grundvorlesung zur Theoretischen Informatik sind daher hilfreich. Alle verwendeten Begriffe werden aber in der Vorlesung (oder Übung) eingeführt.

Termin

Vorlesung: montags, 10-12 h, H 6, Beginn 25.10.;
Übung: freitags, 10-12 h, HZ 201, Beginn 29.10.  (nicht wie im Vorlesungsverzeichnis angegeben, 05.11.)