No label defined (Q4520107)

Der Autor charakterisiert das Buch im Vorwort als ``eine Einführung in die Komplexitätstheorie, die auch für Nichttheoretiker noch lesbar ist. Es führt gleichzeitig auf ausgewählten Gebieten an den aktuellen Forschungsstand heran.'' Genauer geht es um Berechnungskomplexität auf der Grundlage des Berechnungsmodells der Turingmaschine, und es werden hauptsächlich die Komplexitätsmasse Zeit und Raum betrachtet. In den ersten vier Kapiteln (mit etwa 100 Textseiten) wird in zügiger, an den grundlegenden Ideen und Zusammenhängen orientierter Darstellungsweise im wesentlichen das Fundament der klassischen Komplexitätstheorie entwikkelt: 1. Zeit- und Raumkomplexitätsklassen, Blumsche Axiome, Hierarchie- und Lückensätze, Bandkompression und Beschleunigung, Beweisbeispiele für untere Schranken; 2. die Komplexitätsklassen L, NL, P, NP und PSPACE, Reduzierbarkeiten zwischen Sprachen und vollständige Probleme in NL, P und NP; 3. polynomialzeitbeschränkte tt- und T-Reduzierbarkeit, Polynomialzeithierarchie, alternierende Turingmaschinen und Komplexitätsklassen, Relativierungen des P-NP-Problems, das Konzept der Blattsprachen; 4. Sätze von Savitch bzw. Immerman/Szelepcsenyi, blockrespektierende Turingmaschinen und ein Pebble-Spiel auf Graphen führen zur raumeffizienten Simulation zeitbeschränkter Maschinen, DLINTIME \(\subset\) NLINTIME, D \(\not=\) ND für linear zeitbeschränkte Turingmaschinen. Kapitel 5 ergänzt dieses Fundament durch die Problematik der dünnen vollständigen bzw. harten Sprachen für NP und verwandte Klassen bezüglich verschiedener Reduzierbarkeiten. Es ergeben sich Zusammenhänge zu nichtuniformen Komplexitätsklassen wie auch zum Isomorphieproblem, ob alle NP-vollständigen Mengen untereinander polynomial isomorph sind. Der zweite Teil des Buches behandelt dann ausgewählte Themenkomplexe, zu deren Entwicklung und Untersuchung der Autor meist selbst wesentlich beigetragen hat. Wir versuchen, die Inhalte stichpunktartig zu umreißen: Kapitel 6 beschäftigt sich ausführlich mit der Hausdorffschen Hierarchie über NP, auch als Boolesche Hierarchie bekannt. Ihre Klassen werden durch geeignete Akzeptierungstypen und spezielle tt-Reduzierungen auf NP charakterisiert sowie vollständige Probleme angegeben. Enge Beziehungen zur Fragehierarchie, Betrachtungen zum Kollabieren der Hierarchie und zur Reihenfolge von Orakelabfragen ergänzen das Bild. Die im Kapitel 7 betrachteten Zählklassen werden durch Forderungen an die Anzahl akzeptierender Pfade definiert. Diese Verallgemeinerungen des Akzeptierungsverhaltens bei NP und coNP liefert spezielle Blattsprachen. Ein typisches Beispiel ist die Paritätsklasse \(\oplus\)P. Zusätzlich geforderte Eigenschaften der akzeptierenden Maschinen liefern die sogenannten promise-Klassen, wie beispielsweise Valiants UP. Die probabilistischen Komplexitätsklassen, deren Studium das 8. Kapitel gewidmet ist, können ebenfalls häufig als Zählklassen aufgefasst werden. Die Darstellung als Blattsprachen, die mit Hilfe von Quantoren unter Einbeziehung des Mehrheitsquantors definiert werden, führt auch auf die Arthur-Merlin-Klassen. Das Studium entsprechend definierter Operatoren auf Komplexitätsklassen mündet in Ergebnissen von Toda über Beziehungen zwischen probabilistischen Klassen und der Polynomialzeithierarchie. Komplexitätstheoretische Untersuchungen zur Berechnung von Relationen bzw. Funktionen durch deterministische oder nichtdeterministische Maschinen stellen eine naheliegende Verallgemeinerung der vorwiegend auf Entscheidungen und Erkennungen ausgerichteten herkömmlichen Komplexitätstheorie dar. Kapitel 9 gibt die hierzu bekannten Resultate wider. So liefert die Anzahlbestimmung von Lösungen von Berechnungsproblemen, die zu Entscheidungsproblemen gehören, die Klasse \(\sharp P\). Der Wunsch, Lösungen zu konstruieren, führt auf Betrachtungen zur Selbstreduzierbarkeit von Mengen und zur Suche nach optimalen Lösungen. Wieder ergeben sich enge Zusammenhänge zur klassischen Theorie. Das abschließende Kapitel 10 ist den low- und high-Hierarchien gewidmet und diskutiert das Problem der Graphisomorphie. Zusammenfassend ist festzustellen, dass das vorliegende Buch seine Zielstellung, eine nützliche Ergänzung der vorhandenen Lehrbücher und Monographien zur Komplexitätstheorie zu sein, voll erreicht. Die sehr kompakte Darstellung der grundlegenden Resultate in den ersten fünf Kapiteln ist als Richtschnur und begleitende Lektüre für entsprechende Vorlesungen sehr zu empfehlen. Die in den Kapiteln 6 bis 9 behandelten Themenkomplexe sind hier erstmals in monographisch zusammenfassender Weise präsentiert, wodurch sich dieser Teil als Grundlage und Handbuch für speziellere Lehrveranstaltungen und Forschungsseminare empfiehlt.