Seite 3: "Seiner Meinung nach ist P gleich NP."

Inhaltsverzeichnis

Es dauerte nicht lange, nachdem Turings Ideen – und ähnliche Konzepte anderer Forscher – in den ersten Computern ihren Niederschlag gefunden hatten, bis sich die Wissenschaftler mit Fragen zu den inhärenten Fähigkeiten und Grenzen dieser Maschinen auseinandersetzten. Bereits in den frühen 1950er-Jahren prahlte John von Neumann, der ungarisch-amerikanische Pionier des modernen Computers, damit, dass ein von ihm entwickelter Algorithmus polynomial sei, "verglichen mit dem exponentiellen Amtsinhaber", wie sich Papadimitriou erinnert – er hatte einen langsamen Algorithmus mit einem schnellen überlistet. Dies war der Beginn einer neuen Theorie: der Theorie der rechnerischen Komplexität. Denn nur polynomiale Algorithmen galten in irgendeiner Weise als gut oder praktisch verwertbar, während ein exponentieller Algorithmus, so Papadimitriou, "das algorithmische Äquivalent des Todes ist".

Auf der Suche nach dem Generalschlüssel

Cook begann Mitte der 1960er-Jahre, über Komplexität nachzudenken. 1967, während eines Postdoc-Aufenthalts in Berkeley, notierte er erste Ideen, die den Keim seines großen Ergebnisses enthielten. Er hatte eine Formulierung der Komplexitätsklassen ausgearbeitet, die später als P und NP bekannt wurden, und er stellte die Frage, ob P gleich NP sei. Etwa zur gleichen Zeit beschäftigten sich andere, darunter der Informatiker Jack Edmonds, der inzwischen an der University of Waterloo im Ruhestand ist, mit denselben Ideen.

Aber das Gebiet der Informatik war gerade erst im Entstehen begriffen, und für die meisten Wissenschaftler und Mathematiker waren solche Ideen geradezu fremdartig. Nach vier Jahren an der mathematischen Fakultät von Berkeley wurde Cook zwar für eine Festanstellung in Betracht gezogen, aber ihm wurde keine Stelle angeboten. 1970 wechselte Cook daher an die University of Toronto. Im folgenden Jahr veröffentlichte er seinen Durchbruch. Das Paper, das er im Mai auf einem Symposium der ACM in Shaker Heights, Ohio, vorlegte, schärfte das Konzept der Komplexität noch einmal und ermöglichte erstmals, die schwierigsten Probleme zu charakterisieren. Denn Cook bewies, dass das "Erfüllbarkeitsproblem der Aussagenlogik" (SAT, von englisch "satisfiability" = "Erfüllbarkeit") im Sinne der Theorie das schwierigste Problem in NP ist und sich alle anderen NP-Probleme darauf reduzieren lassen (das SAT beschäftigt sich mit der Frage, ob es für eine gegebene aussagenlogische Formel F einen Satz logischer Variablen gibt, für die F logisch wahr ist). Dies war ein entscheidendes Theorem, denn es bedeutet andererseits: Wenn es einen Algorithmus gäbe, der das Erfüllbarkeitsproblem in Polynomialzeit löst, würde dieser Algorithmus als Generalschlüssel dienen, der die Lösungen für alle Probleme in NP aufschließt. Und wenn es eine Polynomialzeitlösung für alle Probleme in NP gibt, dann ist P = NP.

1972 wies Dick Karp, Informatiker der University of California in Berkeley, nach der Lektüre von Cooks esoterischem Aufsatz nach, dass viele der klassischen Rechenprobleme, mit denen er bestens vertraut war – im Grunde jedes Problem aus den Bereichen mathematische Programmierung, Operations Research, Graphentheorie, Kombinatorik und Computerlogik, von dem er nicht wusste, wie es zu lösen war – dieselbe Umwandlungseigenschaft besaßen, die Cook beim Erfüllbarkeitsproblem gefunden hatte. Insgesamt fand Karp 21 Probleme, darunter das Knapsack-Problem (die Suche nach dem optimalen Weg, einen begrenzten Raum mit den wertvollsten Gegenständen zu füllen), das Travelling-Salesman-Problem (die Suche nach der kürzest möglichen Route, die jede Stadt einmal besucht und zur Ausgangsstadt zurückführt) und das Steinerbaumproblem (die Suche nach der optimalen Verbindung einer Menge von Punkten mit Liniensegmenten von minimaler Gesamtlänge).