Vorlesungen zur Komplexitätstheorie

Elementare Resultate aus der Komplexitätstheorie werden in diesem Buch ebenso behandelt wie auch die Themen Polynomialzeithierarchie, probabilistische Klassen oder die Hausdorffsche Hierarchie, Funktionalklassen und Zählklassen. Das Buch ist aus mehrjährigen Vorlesungen des Autors über Komplexitätstheorie entstanden.

In diesem Buch werden sowohl elementare Resultate aus der Komplexitätstheorie behandelt als auch Themen wie Polynomialzeithierarchie, probabilistische Klassen oder die Hausdorffsche Hierarchie, Funktionalklassen und Zählklassen. Das Buch ist aus mehrjährigen Vorlesungen des Autors über Komplexitätstheorie entstanden.

Autorentext

Prof. Dr. Gerd Wechsung, Universität Jena

Inhalt
Hierarchiesätze - Untere Schranken - Raum- und Zeitklassen unterhalb von PSPACE - Polynomialzeithierarchie - Hausdorffsche Hierarchie - Zählklassen - Probabilistische Klassen - Funktionenklassen - Dünne vollständige Mengen - low- und high-Hierarchie