Update (13.8.10): Inzwischen gibt es sehr ernsthafte Einwände gegen den angeblichen Beweis, sie stammen von Neil Immerman, einer anerkannten Koryphäe auf dem Gebiet. Näheres im Blog von Richard Lipton!

Mathematiker sind Gefühlsmenschen. Auch zu Fragen, die noch nicht wirklich entschieden sind, haben die meisten eine Meinung, so ganz aus dem Bauch heraus. Im Jahr 2002 äußerten in einer Umfrage 61 von 100 Mathematikern die feste Überzeugung, dass P und NP verschieden sind. Aber Meinungen zählen in der Mathematik nicht – sie ist eine äußerst undemokratische Wissenschaft. Wenn ein einzelner mit strenger Logik daherkommt und eine Aussage hieb- und stichfest beweist oder widerlegt, dann ist es vorbei mit dem Bauchgefühl.

Nun jedoch könnte das Bauchgefühl der Mehrheit von dem indischstämmigen Mathematiker Vinay Deolalikar bestätigt werden. Und Deolalikar noch dazu reich machen: Die amerikanische Clay Foundation 
zählt nämlich P=NP zu den " Millenniumsproblemen "  der Mathematik, deren Lösung jeweils mit einer Million Dollar dotiert ist. 

Auf den ersten Blick ist es ein langes, gut geschriebenes Paper eines ernsthaften Forschers
Richard Lipton, Informatiker

Am vergangenen Freitag hat Deolalikar, der im Forschungslabor von Hewlett Packard in Kalifornien arbeitet, an ausgewählte Kollegen eine E-Mail geschickt: "Ich freue mich, einen Beweis verkünden zu können, dass P nicht gleich NP ist." Im Anhang verschickte er eine Version des Beweises in der Schriftgröße 10 Punkt und eine in 12 Punkt – vielleicht aus Rücksicht auf die Forscher, die schon seit knapp 40 Jahren nach der Lösung des Problems suchen. Es wurde 1971 von den Mathematikern Stephen Cook und Leonid Levin aufgestellt.

Doch worum geht es überhaupt? Letztlich um die Unterscheidung von leichten (P) und schweren (NP) Rechenaufgaben. Für Mathematiker ist eine Aufgabe schwer, wenn zwar ein Lösungsweg bekannt ist, aber die Rechnung selbst auf dem schnellsten Computer länger dauern würde als das Alter des Universums. Ein Beispiel für eine leichte Rechnung ist das schriftliche Multiplizieren. Nimmt man zwei n-stellige Zahlen miteinander mal, dann 
muss man n 2 Multiplikationen ausführen. Doppelt so lange Zahlen verlangen die vierfache Zeit, dreimal so lange die neunfache. Mathematisch gesprochen, lässt sich die Rechnung in "polynomialer Zeit" lösen, die Klasse dieser Probleme heißt P.

Ein schweres Problem ist dagegen das folgende: Ein Müllwagen fährt durch die Stadt und muss eine gewisse Zahl von Recyclingcontainern leeren. Welches ist der kürzeste Weg für eine solche Leer-Tour? Eigentlich ein triviales Problem: Man schaut sich alle möglichen Touren an und wählt die kürzeste aus. Die Sache hat nur den Haken, dass die Zahl der möglichen Touren nicht polynomial wächst, sondern viel schneller. Ihr Wachstum lässt sich nicht einmal mit n 1000 oder n 1.000.000 begrenzen. Das Routenproblem, auch "Traveling-Salesman-Problem" oder "Problem des Handlungsreisenden" genannt, gehört zu einer Klasse von Problemen, die mit NP bezeichnet werden. Sie zeichnen sich  durch eine seltsame Asymmetrie aus: Auch wenn ihre Lösung  "schwer" ist – die Überprüfung einer (vermeintlichen) Lösung ist immer eine "leichte" Aufgabe.

Aber vielleicht gibt es für das Problem des Müllwagenfahrers ja doch eine einfachere Lösung als das sture Ausprobieren – nur war noch niemand so schlau, sie zu finden? Ist das anscheinend schwere Problem vielleicht 
letztlich doch ein leichtes? Diese Frage wird mit dem Kürzel "P=NP" umschrieben: Wenn die Gleichung stimmt, dann gehören die schweren und die leichten Rechnungen letztlich doch zur selben Liga.

Das Handlungsreisendenproblem gehört zu der interessanten Klasse der sogenannten NP-vollständigen Probleme, für die gilt (das zumindest ist bewiesen): Wenn eines dieser Probleme in P liegt, dann gilt das für alle, und P ist tatsächlich gleich NP.