Die meisten Forschenden, die sich mit dieser Materie beschäftigen, glauben mittlerweile, dass P nicht gleich NP ist. Sie lassen nur einen Funken Hoffnung zu, dass sich das Gegenteil bewahrheiten wird. "Ich würde die Wahrscheinlichkeit, dass P gleich NP ist, auf zwei bis drei Prozent schätzen", sagt der Mathematiker Scott Aaronson von der University of Texas, der seit nunmehr rund 20 Jahren über Komplexitätstheorie und die Grenzen von Quantencomputern nachdenkt. "Das sind die Wettchancen, die ich annehmen würde."
- Zahlensysteme erklärt: Reise in die Geschichte der Informatik
- Geschichte: Zweitausend Jahre Rechenhilfen - ein historischer Schnelldurchlauf
- Historische Kryptoanalyse: So knackt man geheime Nachrichten aus dem Vatikan
- Apple-Geschichte: Wie der erste Macintosh entstand
- Die ersten 25 Jahre in der Geschichte der Mikroprozessoren
- Spam: Die Geschichte unerwünschter Werbung
- Computergeschichte: "Ideen von Frauen hätten unsere Welt radikal verändert
Doch das im Juli 2021 veröffentlichte Ergebnis schien ein Beweis für genau diese Unwahrscheinlichkeit zu sein. Aber das Paper war nur der jüngste in einer langen Tradition von Beweisen, die nur scheinbar funktionierten, weil sie logische Fehler enthalten. Tatsächlich handelte es sich um die jüngste Version einer Arbeit, die der Autor in den letzten zehn Jahren mehr als 60-mal auf dem Preprint-Server "arXiv" veröffentlicht hatte. Einen Tag nach der Veröffentlichung wurde die Arbeit aus der Online-Zeitschrift entfernt; dann schien sie kurz wieder aufzutauchen, bevor sie endgültig verschwand – in einer Monty-Python-würdigen Aktion. Der Chefredakteur der Zeitschrift erklärte auf Twitter, dass das Ergebnis abgelehnt worden war, aber durch einen menschlichen Fehler hatte sich der Status des Papers irgendwie von "ablehnen" in "annehmen" geändert, und der Beweis hatte seinen Weg zur Veröffentlichung gefunden.
Eines der sieben ungelösten "Millenium-Probleme"
Als ich Steve Cook Anfang August in seinem Büro auf dem Campus traf, hatte er von diesem jüngsten P-gegen-NP-Beweis-Chaos weder etwas gesehen noch gehört. Der 81-Jährige hatte sich erst vor kurzem zur Ruhe gesetzt, da sein Gedächtnis nachließ. "Deshalb haben wir James hier", sagte er – sein Sohn James, 36, ebenfalls Informatiker, hatte sich für meinen Besuch zu uns gesellt. Steve war gerade dabei, sein Büro zu entrümpeln. In der Mitte des Raums stand ein riesiger Papierkorb, der sich mit alten, vergilbten Ausgaben des Journal of Symbolic Logic füllte. Gleich daneben lag ein Stapel fetter Telefonbücher aus Toronto.
Im Laufe der Jahre hat Cook viele Beweise gesehen, die vorgeben, das P-vs.-NP-Problem zu lösen. Nachdem das Clay Mathematics Institute das Problem im Jahr 2000 zu einem der sieben ungelösten "Millennium-Probleme" ernannt hatte (deren Lösung jeweils mit einer Million Dollar dotiert ist), wurde er mit Nachrichten von Leuten überschwemmt, die glaubten, sie hätten den Sieg errungen. Etwa die Hälfte behauptete, bewiesen zu haben, dass P gleich NP ist; die andere Hälfte ging in die entgegengesetzte Richtung. Vor nicht allzu langer Zeit behauptete eine Person, beides bewiesen zu haben. Aber alle Ergebnisse waren falsch, wenn nicht sogar schlichtweg gefälscht. Cook war der Erste, der in einem Aufsatz von 1971 die Vermutung aufstellte, dass P nicht gleich NP sein könnte (er formulierte es mit einer anderen, damals üblichen Terminologie). Seitdem hat der Forscher eine beträchtliche Menge an Zeit investiert, um seine Vermutung zu beweisen. Erfolg hatte er damit jedoch nicht. Jetzt will sein Sohn James sich der Sache annehmen.
Schon früh interessierte sich James für Mathematik und Computer – im Alter von neun Jahren drängte er seinen Vater, ihm Boolesche Algebra und Logik beizubringen. Vor ein paar Jahren, nachdem er in Berkeley promoviert und bei Google gearbeitet hatte, machte er sich als unabhängiger Forscher selbstständig und konzentrierte sich auf verschiedene Projekte, von denen einige indirekt mit P vs. NP zu tun hatten. Und trotz dieser Erfolgsbilanz ist James, der seinem Vater verblüffend ähnlich sieht, nicht entmutigt, weil er eine so scheinbar endlose Aufgabe geerbt hat. Er betrachtet es wie jedes andere mathematische Unterfangen: Es ist ein lustiges Rätsel. "Es muss doch eine Antwort auf diese Fragen geben", sagt er. "Irgendjemand muss sie doch lösen. Lasst uns das einfach herausfinden. Es hat lange gedauert. Es ist peinlich, dass wir die Antwort noch nicht kennen."
Der fehlende Fortschritt hat die hartnäckige Gemeinschaft der Forschenden nicht davon abgehalten, das 50-jährige Bestehen der Komplexitätstheorie zu feiern. Die Feierlichkeiten begannen 2019, als sich ihre Anhänger aus der ganzen Welt am Fields Institute for Research in Mathematical Sciences an der University of Toronto zu einem Symposium zu Cooks Ehren versammelten. Christos Papadimitriou, ein Informatiker an der Columbia University, der einen Großteil seiner Karriere mit der Erforschung von P vs. NP verbracht hat, eröffnete die Veranstaltung mit einem öffentlichen Vortrag.
Auch Turings Maschine liefert keinen Wahrheitsbeweis
Schon Alan Turing, erklärte Papadimitrious, der britische Mathematiker, der 1936 in seiner Schrift "On Computable Numbers" die Begriffe "Algorithmus" und "Berechnung" formalisiert hatte, legte die wissenschaftlichen Grundlagen. Denn Turing ersann zwar eine hypothetische universelle Rechenmaschine. Er bewies in dieser Arbeit aber auch mathematisch, dass es keinen "mechanischen" (das heißt von einer Maschine durchführbaren) Weg gibt, die Wahrheit oder Falschheit mathematischer Aussagen zu beweisen; keinen systematischen Weg, das Beweisbare vom Unbeweisbaren zu unterscheiden.
Turings Arbeit sei daher nicht nur Geburtsurkunde der Informatik. "Die Geburtsurkunde besagt auch, dass die Informatik mit einem klaren Verständnis ihrer eigenen Grenzen geboren wurde." Damit sei die Informatik der einzige bekannte Bereich des wissenschaftlichen Diskurses, der mit einem solchen Bewusstsein geboren wurde – "im Gegensatz zu anderen Wissenschaften, die ihre eigenen Grenzen wie wir alle erst im späten mittleren Alter erkennen".
