Complexity Theory Exploring the Limits of Efficient Algorithms

Am Fachwissen von Ingo Wegener ist nicht zu zweifeln, auch in diesem Buch über sein Forschungsgebiet Komplexitätstheorie nicht. Es ist eine Einführung in die NP-Vollständigkeitstheorie vorhanden, doch geht das Buch schnell und weit darüber hinaus und geht zu Approximationsalgorithmen, PCP-Theorem, Blackboxkomplexität und unteren Schranken für Schaltkreisgröße und -tiefe über. Wer also nur mal wissen möchte, was überhaupt die Klasse NP ist, sollte sich bei leichterer Literatur umschauen. Der Stil des Buches ist knapp. Es wird Wert auf die formale Korrektheit und die Beweisführung gelegt. Dementsprechend kann man das Buch nicht so einfach durchlesen, es ist schon eben eine Theorie, die "komplex" ist, wie der Titel es auch vermuten lässt. In Hinsicht und mit Rücksicht darauf ist das Buch gut geschrieben, allerdings sind die 18 Abbildungen auf 300 Seiten einfach etwas zu wenig, um sich das ganze Veranschaulichen zu können. Positiv ist, das Ingo Wegener eine Menge an Stoff in diesem Buch abdeckt.