Computers & Intractability: A Guide to the Theory of NP-completeness
Schwierigkeitsgrad: Schwer
Autoren: Michael R. Garey, David S. Johnson
Erscheinungsdatum: 1979
Sprache: Englisch
ISBN: 0-7167-1045-5
340 Seiten
Rezension von Sebastian Gieße
Jedem, der Grundkenntnisse in der Komplexitätstheorie hat und nun seine
Kenntnisse über NP-Vollständigkeit verbessern möchte, dem empfehle ich
"Computers & Intractability: A Guide to the Theory of NP-completeness" von
Garey und Johnson.
Das Buch eignet sich sowohl als Lehrbuch als auch zum Nachschlagen. Zum
Nachschlagen eignet sich vor allem der riesige Anhang, mit mehr als 300
NP-vollständigen Problemen. Dieser ist sinnvoll kategorisiert, sodass man
schnell Probleme finden kann, auch ohne ihre Namen zu kennen. So konnte ich
zum Beispiel unter "A2.1 Spanning Trees" das Problem "Degree Constrained
Spanning Tree" finden, welches ich zum Beweisen der NP-Vollständigkeit von
Aufgabe 1 der 2. Runde des 29. BwInf nutzen konnte.
Das Buch beginnt mit einer netten Geschichte von einem Informatiker, der
keinen schnellen Algorithmus für ein Problem findet, aber zeigen kann, dass
dies nicht daran liegt, dass er ein schlechter Informatiker ist.
Nach der Einführung in Kapitel 1, folgt mit Kapitel 2 ein ausführlicher und
sehr formaler Einstieg in die NP-Vollständigkeit. Ein Problem ist in NP,
wenn die zugehörige Sprache von einer nichtdeterministischen Turingmaschine
in Polynomialzeit entscheidbar ist. Schließlich wird noch der Satz von Cook
(SAT ist NP-Vollständig) bewiesen.
Kapitel 3 vermittelt die Kunst des NP-Vollständigkeitsbeweis. Zunächst wird
die grundlegende Idee hinter einem solchen Beweis erklärt, dann wird die
NP-Vollständigkeit von 6 bekannten und wichtigen Problemen (3-SAT,
3-Dimensional-Matching, Vertex-Cover, Clique, Hamiltonian Circuit und
Partition) bewiesen. Kapitel 3.2 beschreibt allgemein anwendbare Verfahren
zum Beweis von NP-Vollständigkeit und demonstriert diese an Beispielen.
Kapitel 4: Using NP-Completeness to Analyze Problems
Kapitel 5: NP-Hardness
Kapitel 6: Coping with NP-Complete Problems behandelt
Approximationsalgorithmen und vermittelt wie man zeigen kann, dass das
Ergebniss eines solchen Algorithmus maximal k-mal schlechter als das
optimale Ergebniss ist.
Kapitel 7: Beyond NP-Completeness geht auf unterschiedliche Problemklassen,
z.B. P, NP, NPC, co-NPC, PSPACE, DLOGSPACE ein.
Leider habe ich das Buch, weil ich es in der Bibliothek ausgeliehen hatte,
nicht komplett lesen können. Aber nichtsdestoweniger habe ich sehr viel
gelernt. Beim Lesen wird man oft auf Passagen stoßen, die man mehrfach lesen
muss, um sie zu verstehen. Dies liegt aber nicht am Schreibstil der Autoren,
sondern an der Schwierigkeit der Thematik. Die Erklärungen sind gut und
werden durch sinnvolle Abbildungen unterstützt. Wer dieses Buch gelesen und
verstanden hat, der hat fortgeschrittene Kentnisse über NP-Vollständigkeit,
ist in der Lage Probleme als NP-vollständig zu erkennen und dies dann zu
beweisen, weiß wie er mit solchen Problemen umgehen soll und ist in der Lage
andere Fachliteratur zu verstehen.
Das Buch ist ein Klassiker und früher oder später sollte jeder Informatiker
dieses Buch (wenigstens teilweise) lesen.