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.

Diese Einführung in die strukturelle Komplexitätstheorie führt den Leser bis an die aktuelle Forschung heran.

Vorwort
Aktuelle Einführung in die Komplexitätstheorie

Autorentext
Prof. Dr. Gerd Wechsung, Universität Jena

Klappentext

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

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