Wissenschaft Ist ein Jahrtausendproblem der Mathematik gelöst?

Klar ist nur: Ein Spinner ist er nicht. Vinay Deolalikar glaubt eines der Millenniumsprobleme der Mathematik gelöst zu haben. Experten weltweit prüfen nun seinen Beweis.

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. 

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 ² 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 ¹⁰⁰⁰ 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.

Der Mathematiker Deolalikar behauptet dagegen, er habe ein NP-Problem gefunden, von dem er beweisen kann, dass es auf keinen Fall in P liegt. Erklären lässt sich sein Ansatz in ein paar Sätzen nicht, auch prominente Mathematiker geben zu, dass sie ihn nicht "mal einfach so" kommentieren können. Er macht Anleihen bei bislang weit auseinander liegenden Disziplinen – was auch zu erwarten ist, wenn alle nahe liegenden Versuche der letzten Jahrzehnte gescheitert sind.

In einem Wiki stecken nun die Experten der Komplexitätstheorie – zu diesem Zweig der theoretischen Informatik gehört das Problem – die Köpfe zusammen, um das 100-Seiten-Papier zu analysieren. Bislang ist aus diesem virtuellen Konklave weder weißer noch schwarzer Rauch aufgestiegen, bisher bekommt man nur Bauchgefühlaussagen. "Auf den ersten Blick ist es ein langes, gut geschriebenes Paper eines ernsthaften Forschers", mit diesen Worten adelte der angesehene Informatiker Richard Lipton den angeblichen Beweis. Mathematische Blogger bestätigen, dass die Arbeit "den Nonsenstest" besteht, also keinen offensichtlichen Unsinn eines Spinners darstellt.

Die vorherrschende Gefühlslage geht allerdings dahin, dass Deolalikar zwar einen interessanten Beitrag zur Lösung des Problems geleistet hat, dass allerdings die Löcher, Lücken und Irrtümer (von denen einige schon gefunden wurden) das Werk letztlich auseinanderfallen lassen werden. Der Informatikprofessor Scott Aaronson vom Massachusetts Institute of Technology (MIT) im amerikanischen Cambridge ist sogar bereit, darauf zu wetten: Wenn das Clay-Institut den Beweis tatsächlich akzeptiert und mit einer Million Dollar honoriert, dann legt er selber noch einmal 200.000 Dollar aus der eigenen Tasche drauf. "Wenn tatsächlich bewiesen wird, dass P ungleich NP ist", sagt Aaronson, "dann wird sich mein Leben so dramatisch ändern, dass die 200.000 Dollar nebensächlich sind."

Aber wie gesagt, das alles sind vorerst nur gefühlte Einschätzungen, die nicht viel mehr wert sind als die völlig aus der Luft gegriffene Prognose, die der deutsche Mathematiker Günter Ziegler in seinem vor
ein paar Monaten erschienenen Buch "Darf ich Zahlen?" gemacht hat: Das Problem werde 2012 von einem jungen Inder gelöst. In Zieglers Vision findet der Forscher allerdings eine dritte Antwort auf die Jahrtausendfrage: Sie sei beweisbar unbeweisbar.

Der Artikel wurde gegenüber der usprünglichen Version verändert (ein Fehler in der Definition der NP-Vollständigkeit).