Norbert Blum hat das Problem geknackt. Glaubt er. Vor zwei Wochen stellte der Bonner Informatikprofessor auf der Wissenschaftsplattform Arxiv (Cornell University Library, 2017) eine mathematische Arbeit zur Diskussion. Darin will er beweisen, dass P und NP zwei verschiedene mathematische Objekte sind. Falls das stimmt, wäre eine der wichtigsten mathematischen Fragen der Gegenwart beantwortet – doch die Community ist skeptisch.

Blums Beweis ist der jüngste in einer langen Reihe von Versuchen in den vergangenen Jahrzehnten. Vor ihm glaubten schon Hunderte Autoren, die P- und NP-Frage geknackt zu haben. Aber sie mussten die Kollegen hinterher von der Richtigkeit ihrer Argumentation überzeugen. Bislang schaffte es niemand.

Der Mathematiker Gerhard J. Woeginger sammelt seit 1986 auf seiner Website Beweisversuche zur P- und NP-Frage. 116 Arbeiten hat er gefunden. 49 Autoren wollten zeigen, dass P und NP nicht dasselbe sind, 61 das Gegenteil beweisen. Die übrigen sechs plädierten für Unentschieden. Überzeugend war keiner.

Mathematik - Die Last des Paketboten Was ist einfach, was ist kompliziert? Darum geht es in der P-NP-Frage, die Mathematiker seit Jahrzehnten quält. Wir erklären Ihnen, worum es geht.

Sicher ist: Die P- und NP-Frage ist eine Kernfrage der Wissenschaft. Hinter den Buchstaben verbergen sich Typen mathematischer Probleme: P (polynomiale Rechenzeit) sind die Probleme, bei denen sich eine mathematische Lösung durch einen Algorithmus schnell finden lässt. Bei NP-Problemen (nicht-deterministisch/polynomiale Rechenzeit) lässt sich dagegen eine angebliche Lösung rasch überprüfen. Aber: Zum Finden einer optimalen Lösung ist bislang für kein NP-Problem ein schneller Algorithmus bekannt. Die Kernfrage ist daher: Unterscheiden sich P- und NP-Probleme grundsätzlich in ihrer Schwierigkeit?

Die Frage ist tatsächlich für das tägliche Leben von Bedeutung: Jedes Handy hat ständig Hunderte P- und NP-Probleme zu lösen. Das Sortieren von Zahlen ist ein einfaches P-Problem. Auch die Suche nach dem kürzesten Weg zwischen zwei Städten – die Kernaufgabe eines Navi – ist schnell zu lösen. Die Algorithmen dafür spucken die Lösung nach wenigen Augenblicken aus. Doch kleine Änderungen in der Aufgabenstellung können aus der Routensuche ein NP-Problem machen: etwa, wenn die Route durch viele vorgegebene Städte auf einer Landkarte führen und dabei keinen Weg zweimal benutzen soll. Das interessiert zum Beispiel Paketfahrer.

Solange es um einige Hundert Adressen geht, lassen sich die Routen von Paketauslieferern noch einigermaßen schnell berechnen. Doch die Algorithmen werden langsam, wenn die Routen zu lang werden. Ein Beispiel liefert der dänische Mathematiker Keld Helsgaun: Seit 2013 hält er den Rekord für die schnellste Rundroute durch 1,9 Millionen Städte auf der ganzen Erdkugel. Man weiß, dass Helsgauns Route nicht die kürzeste sein kann. Wie aber eine kürzere Rundroute aussieht, ist unklar. Die Suche nach Lösungen dieser Größenordnung dauert mit den gängigen Algorithmen Monate.

Bekommt man allerdings eine Rundroute als Lösung angeboten, dann ist es ein Klacks, zu testen, ob sie kürzer ist als Helsgauns Route – es reicht ja, die Längen der Streckenabschnitte zusammenzuzählen. Das geht schnell. Genau das zeichnet alle NP-Probleme aus: Man kann eine angebliche Lösung schnell testen, nur finden lässt sie sich offenbar nicht.