Bonn/Wien – So richtig berühmt ist das sogenannte P-NP-Problem-Problem erst seit den 1970er Jahren und dem Anbruch des Computerzeitalters. Doch zumindest zwei der größten Denker des 20. Jahrhundert haben schon rund 20 Jahre früher Versionen davon formuliert: John Forbes Nash ("A Beautiful Mind") 1950 in einem Brief an die National Security Agency, in dem es um Kryptographie ging, sowie der aus Wien stammende Logiker Kurt Gödel sechs Jahre später in einem Schreiben an den Computerpionier John von Neumann.

Worum geht es bei diesem Problem, das eines der sieben Millienniums-Probleme ist, für deren Lösung das Clay Mathematics Institute im Jahr 2000 je eine Million US-Dollar auslobte? Es handelt sich dabei um eine Frage aus dem Gebiet der Komplexitätstheorie; etwas konkreter geht es um das Problem, wie schnell ein Computer Aufgaben bestimmter Komplexität lösen kann. Dabei unterscheidet man zwischen sogenannten P-Problemen und NP-Problemen.

Der Unterschied zwischen P und NP

P-Probleme lassen sich in sogenannter "polynomieller" Zeit berechnen. Anders gesagt: Der Aufwand für die Lösung nimmt in vertretbarem Ausmaß zu, wenn der zu berechnende Input wächst. Zum Beispiel nimmt der Rechenaufwand, um zwei Zahlen mittels eines simplen Algorithmus miteinander zu multiplizieren, etwa mit dem Quadrat der Anzahl Stellen der beiden Zahlen zu. Multiplikation und andere arithmetische Operationen wachsen somit polynomartig und gehören damit zur Klasse P: Sie können also in "vertretbarer" Zeit gelöst werden.

Bei andere Aufgaben wächst die Schwierigkeit viel schneller als polynomartig. Zum Beispiel nimmt der Rechenaufwand, um eine Zahl in ihre Primfaktoren zu zerlegen (etwa 15 in 5 und 3) mit der Länge der Zahl extrem schnell zu. Das macht man sich heute etwa bei der Verschlüsselung von Kreditkartennummern im Internet zunutze, da auch die schnellsten Computer Primfaktoren mit den derzeit bekannten Algorithmen nicht in vertretbarer Zeit finden können, wenn die zu zerlegende Zahl genügend groß ist – im Fall der Kreditkarten sind das Zahlen mit 256 Stellen.

Umgekehrt kann man bei einem NP-Problem die Richtigkeit der Lösung schnell überprüfen, wenn man diese erst einmal kennt, ähnlich wie beim Sudoku.

Das Problem im Videoformat

Das eigentliche P-NP-Problem besteht nun in der fundamentalen Frage, ob P gleich NP ist oder nicht. Wäre Ersteres der Fall, würde das bedeuten, dass es sich bei NP-Problemen in Wahrheit um Fragen handelt, die sich mit bestimmten Tricks, die wir nur noch nicht kennen, ebenfalls in polynomieller Rechenzeit lösen ließen.

Diese Frage, die für viele als die wichtigste der Informatik überhaupt gilt, hat auch Eingang in die Populärkultur gefunden (nämlich unter anderem in eine Folge der "Simpsons"), wie der britische Physiker und Bestsellerautor Simon Singh in einem amüsanten Video erläutert und nebenbei auch noch eine gute Erklärung des Problems mitliefert:

Eine andere anschauliche, aber etwas anspruchsvollere Darstellung des Problems im Videoformat findet sich hier:

P gleich NP?

Mathematiker und Informatiker halten es für ziemlich unwahrscheinlich, dass P gleich NP ist. Würde allerdings das Gegenteil bewiesen werden, hätte das einerseits ungeahnte Folgen für die Mathematik. Andererseits wäre das beispielsweise für die heute gängigen Methoden der Verschlüsselung katastrophal: Würde es sich bei der Primzahlzerlegung in Wirklichkeit auch um ein P-Problem handeln, könnten Computer mit neuen, noch unbekannten Algorithmen bisherige Verschlüsselungen vergleichsweise flott knacken können. (Und wir reden hier nicht von Quantencomputern.)

Blums Beweis und die Folgen

Der Bonner Mathematiker Norbert Blum hat vor gut einer Woche einen Beweis auf der Preprint-Plattform "arXiv" publiziert, der für Laien unverständlich ist und der die konventionelle Annahme der Mathematiker bestätigt und den Kryptographen und Kreditkartenunternehmen zur Beruhigung gereicht – wenn er denn stimmt und vollständig ist: In seiner 38-seitigen Beweisführung kommt Blum nämlich zum Schluss, dass P ungleich NP ist.: NP-Probleme sind demnach also grundsätzlich anders als P-Probleme.

In Konsequenz bedeutet das auch, dass es für bestimmte NP-Probleme einfach keine Algorithmen gibt, um sie in "vertretbarer" Zeit zu lösen – egal, wie lange man noch nach diesen Algorithmen sucht.

Für Blum selbst gäbe es eine Million US-Dollar, falls der Beweis auch tatsächlich stimmen sollte. Und über diese letzte Frage diskutieren seit dem 11. August Informatiker und Mathematiker in aller Welt mit großer Heftigkeit. Noch ist die Fachwelt einigermaßen gespalten – und auch durchaus angetan von Blums Versuch. So etwa meinte der Informatiker Reza Zadeh von der Stanford University am Mittwoch auf Twitter:

Zadeh nahm dabei auch Bezug darauf, dass Blums Ansatz dem zweier skandinavischer Informatiker aus dem Jahr 1999 ähnelt, was andere als Problem sehen – wie etwa der Mathematiker Alon Amit auf der Plattform "Quora": Für ein so fundamentales Problem wie P versus NP brauche es einen völlig neuen Ansatz und nicht Variationen bekannter Verfahren.

Die Skepsis scheint zu überwiegen

Im Fachforum von "Theoretical Computer Science Stack Exchange" wird dagegen positiv hervorgehoben, dass Blums Beweis immerhin so gut geschrieben sei, um entweder als richtig oder falsch beurteilt werden zu können. Das unterscheide ihn von vielen bisherigen P-NP-Beweisen, von denen es laut einer inoffiziellen Zählung bisher immerhin schon 116 gibt, die sich letztlich alle als unbrauchbar herausstellten.

Wenig Hoffnung, dass Blums Beweis sich nicht in diese Liste einreihen könnte, vermittelt eine erste Reaktion von Scott Aaronson, der als eine der wichtigsten P-NP-Autoritäten weltweit gilt: Der Informatiker von der University of Texas in Austin wettete auf seinem Blog 200.000 US-Dollar darauf, dass Blums Beweis – so wie alle früheren Versuche – fehlerhaft sei. (tasch, 20.8.2017)

(In einer früheren Version fehlte in diesem Text an der entscheidenden Stelle ein "nicht" bzw. "un-"(gleich) bei Blums Beweis. Danke für die zahlreichen Hinweise im Forum, der Fehler wurde korrigiert.)