Seite 4: Ein Rätsel, "konkret und doch universell"

Inhaltsverzeichnis

Karp zeigte, dass diese speziellen Probleme alle gleichwertig waren, was wiederum darauf hinwies, dass das von Cook identifizierte Muster kein isoliertes Phänomen war, sondern vielmehr eine Klassifizierungsmethode von überraschender Stärke und Reichweite. Es war eine Art Lackmustest, der die Klasse der sogenannten "NP-vollständigen" Probleme identifizierte: Eine Lösung für eines dieser Probleme würde sie alle knacken. Wie es der wissenschaftliche Zufall wollte, kam ein sowjetischer Mathematiker, Leonid Levin, mehr oder weniger zur gleichen Zeit zu einem Ergebnis, das dem von Cook entsprach. Levin, der heute an der Universität Boston lehrt, führte seine Arbeit hinter dem Eisernen Vorhang aus. Nachdem es größere Aufmerksamkeit erlangte (er emigrierte 1978 nach Amerika), wurde das Ergebnis als Cook-Levin-Theorem bekannt.

Probleme in der Komplexitätstheorie, stellt James Cook fest, verhalten sich manchmal wie Dominosteine – wenn es in einer kritischen Ecke einen Beweis gibt, dann fallen auch alle anderen Dominosteine um. Die bahnbrechenden Erfolge sind das Ergebnis einer langen Reihe von Arbeiten vieler verschiedener Leute. Sie machen schrittweise Fortschritte und stellen Verbindungen zwischen verschiedenen Fragen her, bis schließlich ein großes Ergebnis herauskommt.

Widerlegung könnte eine große Enttäuschung sein

Doch auch wenn es gelänge, das Theorem seines Vaters zu widerlegen – ein wirklich teuflisch schneller P = NP-Algorithmus also existieren würde – könnte das Ergebnis eine große Enttäuschung sein: Denn es könnte sich herausstellen, dass ein P-Algorithmus, der in der Lage ist, das NP-komplette Problem zu lösen, auf einer Zeitskala von, sagen wir, n₁₀₀ liegt. "Technisch gesehen fällt das unter P: Es ist ein Polynom", sagt James. "Aber n₁₀₀ ist immer noch sehr unpraktisch" – es würde bedeuten, dass jedes größere Problem in menschlicher Zeit unlösbar wäre. Natürlich nur, wenn wir den Algorithmus überhaupt finden können. Donald Knuth, mittlerweile emeritierter Informatik-Professor der Stanford University und Autor des Standardlehrbuchs "The Art of Computer Programming", hat in den letzten Jahren seine Meinung zu dieser Frage geändert – das "Bit umgedreht", wie er sagt. Seiner Meinung nach ist P tatsächlich gleich NP, aber wir werden diese Tatsache praktisch nie nutzen können, weil wir keinen der Algorithmen kennen, die tatsächlich funktionieren. Es gäbe eine unvorstellbar große Anzahl von Algorithmen, erklärt er, aber die meisten von ihnen seien für uns nicht zugänglich, weil der Suchraum schlicht zu groß sei. Während also einige Forscher darauf bestehen, dass es keinen P = NP-Algorithmus gibt, behauptet Knuth, dass "es wahrscheinlicher ist, dass kein Polynomialzeit-Algorithmus jemals von Normalsterblichen verkörpert, das heißt tatsächlich als Programm niedergeschrieben wird".

Für Papadimitriou würde jede Antwort eine lebenslange Besessenheit stillen. Seiner Meinung nach gehört das P-vs.-NP-Problem in den Bereich grundlegender wissenschaftlicher Rätsel wie der Suche nach dem Ursprung des Lebens oder der Theorie, die alle vier Grundkräfte der Natur auf eine einheitliche Wechselwirkung zurückführt. Es ist die Art von tiefgründigem, folgenreichem Rätsel, "konkret und doch universell", sagt er, "das nicht nur der Wissenschaft, sondern auch dem menschlichen Leben selbst einen Sinn verleiht". "Stellen Sie sich vor, dass wir Glück haben und es uns gelingt, trotz aller Widrigkeiten und trotz aller Ungereimtheiten noch ein paar tausend Jahre aus diesem Planeten herauszuquetschen", sagt er. "Und wir lösen diese Probleme nicht. Was hätte das für einen Sinn?!"

(wst)