Komplexitätstheorie (Vorlesung)

Entscheidbare Probleme lassen sich bezüglich verschiedener Parameter klassifizieren. Beliebte Klassifikationen passieren bezüglich Rechenzeitverbrauch und Speicherplatzbedarf. Beide Parameter basieren auf einem festen Algorithmenbegriff, in unserem Fall der Turing-Maschine, und Rechenzeit und Speicherplatz beschreiben den Verbrauch einer Ressource. Einschränkungen an den Ressourcenverbrauch definieren sogenannte Komplexitätsklassen. Ein wichtiges Anliegen der Komplexitätstheorie ist die Untersuchung von Komplexitätsklassen hinsichtlich sowohl ihrer Eigenschaften untereinander als auch der Eigenschaften der enthaltenen Probleme.

Vorlesungsinhalt

Wir werden zwei Algorithmenmodelle untersuchen, nämlich deterministische Turing-Maschinen und nichtdeterministische Turing-Maschinen. Beide Modelle erlauben die Definition von Komplexitätsklassen durch Beschränkung der Reichenzeit und des Speicherplatzes. Insbesondere im Falle des nichtdeterministischen Modells sind verschiedene Klassendefinitionen möglich und sinnvoll. Bekannte Komplexitätsklassen, die sich so ergeben, sind L, NL, P, NP, PSPACE, NPSPACE. Wir werden diese und weitere Komplexitätsklassen untersuchen, vorzugsweise bezüglich ihrer Inklusionsstruktur und ihrer (Abschluß-)Eigenschaften.

Ein Hauptaugenmerk im Rahmen dieser Vorlesung wird auf unteren Komplexitätsschranken liegen. Es wird die Frage untersucht werden, wie man untere Schranken beweisen kann (oder auch nicht). Das besondere Resultat dieser Vorlesung wird die Trennung einer deterministischen Komplexitätsklasse von ihrem nichtdeterministischen Analogon beweisen.

Teilnahmevoraussetzungen

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

Termine

Vorlesungmontags, 10 Uhr c.t.H 7
Übungdonnerstags, 12:30 UhrH 405

Dozent

Daniel Meister

Prüfungstermine

Die mündlichen Prüfungen finden ab 19.02.2013 im Büro von Herrn Meister statt. Ab 09.04.2013 sind Nachprüfungen vorgesehen. Im LSF-Portal angegebene Termine sind pro forma; eine konkrete Terminierung erfolgt auf jeden Fall nach Vereinbarung.