Komplexitätstheorie (Vorlesung)

Thema

Eine Einordnung der Komplexitätstheorie in das Umfeld der Theoretischen Informatik sowohl allgemein als auch in Hinsicht auf unser Lehrangebot finden Sie bei den „Lehrinformationen”.

Vorlesungsinhalt

Wir werden drei Algorithmenmodelle betrachten, die von theoretischer und praktischer Bedeutung sind: deterministische, nichtdeterministische und alternierende Turing-Maschinen. Deterministische Turing-Maschinen modellieren reale (Ein-Prozessor-)Rechner, alternierende Turing-Maschinen sind ein Modell für Parallelrechner, und nichtdeterministische Turing-Maschinen spielen eine wichtige Rolle bei der Klassifikation der meisten bekannten Berechnungsprobleme.

Für jedes der drei Algorithmenmodelle werden wir Komplexitätsmaße definieren, die den Ressourcenverbrauch eines Problems messen. Durch Beschränkung dieser Maße entstehen Komplexitätsklassen, die Probleme ähnlichen Ressourcenverbrauchs zusammenfassen. Bekannte und bedeutende solche Komplexitätsklassen sind L, NL, AL, P, NP, AP, PSPACE, NPSPACE. Diese werden auch in der Vorlesung von Bedeutung sein.

Wir werden untersuchen, wie sich Komplexitätsklassen zueinander verhalten, insbesondere wenn sie auf unterschiedlichen Algorithmenmodellen basieren. Die zur Untersuchung verwendeten Techniken lassen sich als (einfache) Compiler und deren Qualitätsanalyse verstehen. Wir werden auch sehen, daß bei solchen Untersuchungen nicht jede Ressourcenbeschränkung sinnvoll erscheint.

Ein besonderes Interesse der Vorlesung liegt im Bereich von unteren Schranken, die einen Mindestressourcenbedarf für das Lösen eines Problems angeben. Solche Resultate sind selten, und die Suche danach stellt eine der zentralen Herausforderungen der Forschung dar.

Teilnahmevoraussetzungen

Die betrachteten Berechnungsmodelle basieren auf Turing-Maschinen; Kenntnisse aus der Grundvorlesung zur Theoretischen Informatik sind hilfreich. Ein Interesse an den Grundfragen der Theoretischen Informatik sollte vorhanden sein.

Alle verwendeten Begriffe werden in der Vorlesung (oder Übung) eingeführt.