Es gilt als das größte Rätsel der modernen Informatik. Der amerikanische Computerexperte Scott Aaronson hält es gar für die "tiefschürfendste Frage, die sich Menschen je gestellt haben". Nun hat der Bonner Mathematikprofessor Norbert Blum einen mathematischen Beweis ins Internet gestellt, der das Jahrhundertproblem lösen soll. "A Solution of the P versus NP Problem" ist 38Seiten lang und für Laien wohl nur schwer nachvollziehbar.
Demjenigen, der eine korrekte Lösung findet, winkt neben dem Ruhm auch viel Geld: Das so genannte P-NP-Problem zählt zu den sieben Millennium-Problemen, für deren Lösung das Clay Mathematics Institute im Jahr2000 eine Million US-Dollar in Aussicht gestellt hat.
Sollte Blums jetzt veröffentlichte Argumentation stimmen, wäre die Tragweite gewaltig: Der Forscher glaubt, beweisen zu können, dass P ungleich NP ist. Das wäre eine Enttäuschung für Zahlenforscher, eine Erleichterung für Kryptografen– und in jedem Fall ein Ergebnis für die Geschichtsbücher.
Auf die Komplexität kommt es an
Im Kern des P-NP-Problems steht die Frage, wie schnell ein Computer Aufgaben bestimmter Komplexität lösen kann. Informatiker unterscheiden hier P-Probleme und NP-Probleme. P-Probleme lassen sich in polynomieller Zeit berechnen. Man könnte auch sagen: Der Aufwand für die Lösung nimmt in vertretbarem Ausmaß zu, wenn der zu berechnende Input wächst. Mathematisch entspricht das der Beziehung nk, wobei n die Eingabelänge bezeichnet und k eine Konstante ist. Ein Beispiel ist die Frage, ob eine Zahl mit nZiffern eine Primzahl ist– das können moderne Algorithmen mit vergleichsweise wenigen Rechenschritten prüfen.
Eine anschauliche Erklärung des P-NP-Problems
Anders sieht es aus, wenn der Aufwand für die Lösung eines Problems exponentiell anwächst, etwa nach dem Schema 2n. Solche Aufgaben werden teilweise so umfangreich, dass sie kein Rechner der Welt mehr mit vertretbarem Zeitaufwand lösen kann. Die Komplexitätsklasse NP ist hier nochmal ein Sonderfall: Sie umfasst "nichtdeterministisch polynomielle" Probleme. Darunter verstehen Informatiker Aufgaben, die mit deterministischen Rechnern rasant an Komplexität zuzunehmen scheinen.
Deterministisch ist ein Rechner dann, wenn er Rechenschritte nacheinander ausführt, und nicht alle denkbaren Lösungswege auf einmal ausprobieren kann– de facto sind also alle heutigen Computer deterministisch. Sie können bei einem NP-Problem zwar rasch überprüfen, ob eine Lösung stimmt. Die korrekte Lösung zu finden erfordert aber mitunter eine sehr lange Suche, schließlich muss ein deterministischer Rechner alle möglichen Wege sukzessive durchprobieren.
Ein extremes Beispiel für ein NP-Problem ist ein Handlungsreisender, der eine Reihe von Städten besuchen will, dabei aber eine möglichst kurze Strecke zurücklegen soll. Die Anzahl der Möglichkeiten, die ein Computer bei der Berechnung der kürzesten Strecke prüfen muss, wächst hier mindestens exponentiell mit der Zahl der zu besuchenden Städte. Ein Albtraum für jede Maschine. (Tatsächlich ist der Handlungsreisende so knifflig, dass Experten von einem NP-schweren Problem reden).
Für Mathematiker würde ein Traum platzen
Vielleicht gehen Informatiker Aufgaben wie diese aber auch einfach nur falsch an: Handelt es sich bei NP-Problemen in Wahrheit um Fragen, die sich mit Tricks in polynomieller Rechenzeit lösen ließen? Darauf liefe es hinaus, wenn P gleich NP ist. Das halten Informatiker für ziemlich unwahrscheinlich. Die Folgen wären allerdings gewaltig, denn auch das Knacken gängiger Verschlüsselungskodes ist ein NP-Problem. Würde es sich dabei in Wirklichkeit um ein P-Problem handeln, wäre es womöglich nur eine Frage der Zeit, bis Computer viele Kryptografieverfahren aushebeln, schreibt Scott Aaronson in einer Analyse des Problems.
Sollte der Beweis von Norbert Blum stimmen, könnten Computerexperten in aller Welt aufatmen. Für manchen Mathematiker würde hingegen wohl ein Traum platzen: Auch die Fahndung nach mathematischen Beweisen ist ein NP-Problem. Wäre P gleich NP könnte man die Lösungen zu einigen der anderen millionenschweren Millennium-Problemen also einfach von einem Computer suchen lassen.
Ob diese Möglichkeit mit Blums Beweis für alle Zeiten ausscheidet, müssen nun andere Informatiker und Mathematiker beurteilen. Einige von ihnen dürften bereits damit begonnen haben, die Argumentation des Bonner Wissenschaftlers zu prüfen. "Das ist eines der größten Probleme der Informatik überhaupt", sagt Günter Rote, Informatikprofessor von der Freien Universität Berlin.
Frühere Beweise waren schlichtweg unverständlich
Erste Einschätzungen zu Blums Beweis sind schon im Internet aufgetaucht. Der Informatiker Luca Trevisan von der University of California in Berkeley glaubte am Tag nach der Veröffentlichung etwa, einen offensichtlichen Fehler in dem Paper gefunden zu haben, ruderte aber bald darauf zurück. In einem Blogpost skizziert er nun Blums Beweisidee und listet eine Reihe von möglichen Schwächen der Argumentation auf. Bald werde man wissen, ob derartige Einwände berechtigt sind, schreibt Trevisan.
Bei anderen Experten hinterließ die Arbeit hingegen einen guten Ersteindruck: "Hat jemand einen Fehler in dem Beweis gefunden? Norberts letzte Arbeit war großartig", kommentierte etwa der Computerforscher Reza Zadeh von der Stanford University auf Twitter. Ein anonymer Nutzer des Fachforums "Theoretical Computer Science Stack Exchange" hingegen vermerkte: Das Paper sei gut genug geschrieben, um entweder richtig oder falsch zu sein. Das hebe Blums Arbeit von vielen P-NP-Beweisen der Vergangenheit ab, die schlichtweg unverständlich gewesen seien.
Dem pflichtet Rote bei: "Wenn man den Beweis durchblättert, sieht das nicht sonderlich abschreckend aus, sondern so, als könnte man das ohne großen Aufwand nachvollziehen." Blum verwende im Wesentlichen mathematische Konzepte, die bereits seit zehn Jahren bekannt sind– und damit als erprobt gelten.
Es gibt bereits 116Beweise zu P-NP
Für manchen Experten ist das ein Grund, an der Arbeit des Bonner Forschers zu zweifeln. Solch ein großes Problem wie P-NP werde vermutlich durch überraschende neue Kniffe gelöst werden und nicht durch eine Abwandlung bekannter Rezepte, argwöhnte der Mathematiker Alon Amit auf der Plattform "Quora". Blums Ansatz ähnele dem zweier skandinavischer Computerwissenschaftler aus dem Jahr1999.
Mittlerweile hat sich auch Scott Aaronson zu Wort gemeldet, der vielen als Instanz in Sachen P-NP gilt: Er wette 200000US-Dollar darauf, dass der Beweis so wie alle früheren Versuche fehlerhaft ist, schrieb der Computerwissenschaftler von der University of Texas in Austin auf seinem Blog.
Tatsächlich haben in der Vergangenheit etliche Wissenschaftler Beweise zu dem berühmten Informatikproblem vorgelegt. GerhardJ. Woeginger von der RWTH Aachen hat alle bisherigen Versuche aufgelistet und kommt auf insgesamt 116Anläufe. Sie stellten sich letztlich alle als falsch heraus.
Blum selbst will sich noch nicht zu seinem Beweis äußern, teilt er auf Anfrage von "Spektrum.de" mit. Er wolle zunächst abwarten, was seine Fachkollegen zu seiner Arbeit sagen. "Er vertieft sich gerne in schwierige Probleme und löst diese allein", sagt der Berliner Informatiker Günter Rote über seinen Bonner Kollegen. Normalerweise dürfte der Kreis der Leute, die Blums Arbeit kritisch prüfen, überschaubar sein. Diesmal hat er sich aber ein Problem vorgenommen, das Computerexperten in aller Welt fasziniert. Wie ihr abschließendes Fazit ausfallen wird, ist derzeit noch offen.
