Die Komplexitätstheorie untersucht den algorithmischen Aufwand zur Lösung von Problemen mit Hilfe von Maschinen. Im vorliegendem Buch wird zunächst das wichtigste Maschinenmodell - die Turingmaschine - vorgestellt. Verschiedene Typen dieser Maschinen werden behandelt und zu einander in Beziehung gesetzt. Auch grundlegende Begriffe, wie zum Beispiel der Begriff des Komplexitätsmaßes, werden eingeführt und erläutert.

Aber auch alternative Rechnermodelle, wie zum Beispiel die Registermaschinen oder auch Schaltkreismodelle, spielen zunächst eine Rolle. Später stellen sich diese aber als äquivalent zur Turingmaschine heraus.

Einige wichtige Hierarchiesätze und sogenannte Speedup-Sätze sind das Thema des dritten Kapitels.

Im nächsten Kapitel wird die Frage untersucht, welche Auswirkungen die Struktur des verwendeten Speichers auf die Mächtigkeit der Turingmaschinen hat. So steht das Konzept der on-line bzw. off-line Turingmaschine im Vordergrund. Auch auf den Unterschied zwischen 1-dimensionalen und 2-dimensionalen Speicherstrukturen wird eingegangen.

Gegenstand des 5. Kapitels ist das Verhältnis der Ressourcen Zeit und Speicherplatz zueinander. Für viele Probleme zeigt sich, daß man entweder den Zeitbedarf oder den Speicherbedarf reduzieren kann, aber immer auf Kosten der entsprechenden anderen Ressource. Dieses wird auch als Time-Space Tradeoff bezeichnet.

Im letzten Kapitel werden die wichtigsten sequentiellen Komplexitätsklassen vorgestellt. Dazu werden neben den einzelnen Klassendefinitionen auch Beispielprobleme aus den zugehörigen Klassen vorgeführt. Weiterhin wird der Begriff der Vollständigkeit eingeführt und auf die Klasse NP angewandt. Wieder werden einige wichtige Beispiele NP-vollständiger Probleme angegeben. Hier wird auch der Praxisbezug deutlich, da sich einige Probleme, wie zum Beispiel Routenplaner und ähnliches, als NP-vollständige Probleme heraustellen.

Ein dokumentiertes Literaturverzeichnis rundet jedes Kapitel ab.

Ein 2. Band, in dem das Thema „Parallelität und Randomisierung” behandelt wird, ist in Vorbereitung.

André Große