Deutscher soll gerade eines der wichtigsten Informatik-Probleme unserer Zeit gelöst haben

Was haben heilbarer Krebs, ein gerechter Kapitalismus und das fehlerfreie Durchzocken von Super Mario Bros. gemeinsam? Laut einer mathematischen Theorie könnten solche Probleme mit einem Schlag gelöst werden. Man bräuchte nur bessere Algorithmen, die beweisen, dass diese komplizierten Probleme – Proteinfaltung, effiziente Märkte, Spielkombinatorik – letztlich nur Varianten einfacherer Probleme sind, die sich bereits heute mit unseren Supercomputern lösen lassen.

Doch wie kann ein solcher Algorithmus aussehen, der aus extrem schwierigen Aufgaben handhabbare macht? Oder unterscheiden sich komplizierte Probleme grundsätzlich von einfacheren – und Erstere werden sich nie auf Letztere reduzieren und damit berechnen lassen? Dieses Rätsel gehört zu den größten ungelösten Fragen der Mathematik; es ist eins von sieben sogenannten "Millennium-Problemen", für dessen Lösung eine Million Dollar ausgelobt sind.

Nun hat es möglicherweise ein Deutscher geknackt – aber leider überbringt er keine guten Nachrichten. Norbert Blum von der Uni Bonn behauptet in seinem gerade veröffentlichten 38-seitigen Beweis: P ist ungleich NP. In anderen Worten: Komplizierte Probleme sind fundamental unterschiedlich zu den einfacheren Problemen, unsere kompliziertesten Probleme werden auch in naher Zukunft Hochleistungsrechner nicht knacken können.

Blums Schlussfolgerung passt zur populären Meinung in der Wissenschaft. Diese besagt, dass unsere Computer und die Mathematik, auf der sie basieren, zwei Arten von Problemen kennen: die einfachen oder P-Probleme, die in "polynomieller", also vertretbarer Zeit berechnet werden können; und die schwierigen NP-Probleme, die unsere Computer nicht in vertretbarer Zeit lösen können.

Beispiele für NP-Probleme sind etwa:

- die Proteinfaltung: Das Verfahren, bei dem Proteine in einem biologischen Organismus ihre Struktur erhalten. Ein besseres Verständnis des Verfahren könnte Fehler in der Proteinbildung besser entdecken oder gar verhindern – und damit manche Formen von Krebs heilbar machen.

- das Problem des Handlungsreisenden: Ein Städtetrip an 15 verschiedene Orte mit optimaler Reiseroute und ohne eine Stadt zwei Mal zu besuchen? Selbst für Supercomputer eine harte Nuss. Gilt daher ebenfalls als NP-Problem in der Informatik.

- ein perfektes Schachspiel: Das Schachspiel kennt derart viele mögliche Spielzüge, dass selbst die leistungsfähigen Computer keine perfekte Taktik berechnen können. Manche Mathematiker halten die Frage sogar für so schwierig, dass sie sie nicht mal als Teil von NP-Problemen einstufen, sondern außerhalb dieses Möglichkeitsraumes.

Doch all diese harten Nüsse haben eine Gemeinsamkeit: So schwer die Lösungen zu diesen und anderen NP-Problemen zu finden sind, so einfach sind die Lösungen zu überprüfen, sobald man sie hat.

Die Zwei-Klassen-Aufteilung von Problemen hat ihren Ursprung in der Zeit vor dem gesellschaftlichen Durchbruch des "Heimcomputers". In den 70er Jahren, als Computer noch so klobig wie Wandschränke waren, stellte sich bald heraus, dass nicht alle Probleme der Menschheit in ihrer Code-Gestalt gleichermaßen einfach zu berechnen sind. Bald bildeten sich zwei unterschiedliche Klassen von Problemen heraus, die einfacheren P-Probleme und die komplizierteren NP-Probleme.

Streit unter Mathematikern gibt es seitdem um die Frage, ob man nur intelligentere Algorithmen bräuchte, damit die NP-Probleme sich sich in am Rechner zu bezwingende P-Probleme auflösen würden. Schafft es jemand, zu beweisen, dass ein NP-Problem letztlich doch eine Variante von P-Problemen sind, könnte die Lösung eines NP-Problems die Lösung gleich aller anderen NP-Probleme sein. Anders gesagt: Wer weiß, wie die perfekte Taktik bei Super Mario Bros. aussieht, könnte auch Krebs heilen.

Insgesamt 116 Mal haben die Mutigsten ihres Fachs bislang versucht, das Rätsel zu lösen. Bislang wurde keiner von der Mathematik-Community als Beweis anerkannt.

Das Clay Mathematics Institute (CMI) mit Sitz in Cambridge hat im Jahr 2000 die Top7 der ungelösten mathematischen Probleme erstellt und für jede Lösung eines der Probleme eine Millionen Dollar versprochen. Eine Art "Wer wird Millionär?" für Mathematiker.

Die Millennium-Probleme gelten auch in Fachkreisen als ausgesprochen harte Nüsse. Man braucht schon eine ganze Menge Fachwissen, um überhaupt die Frage zu verstehen. Als einziges Millennium-Problem wurde bisher die Poincaré-Vermutung gelöst. Der als eigenbrötlerisch geltende Russe Grigori Perelman verzichtete jedoch auf den Preis und lehnte die Verleihung einer Medaille ab.

Noch ein eher schwieriger Charakter, der versucht hat, die ABC-Vermutung zu lösen: Dieser Mathematiker wütet, weil niemand seinen 500-Seiten-Beweis kapiert

Dass die Lösung von NP-Problemen nicht nur positive Folgen hat, sondern auch zu neuen Problemen führen kann, zeigt das Beispiel der Verschlüsselung von Kreditkarten: Banken machen sich bei der Verschlüsselung von Kreditkartennummern den Umstand zunutze, dass auch die schnellsten Computer extrem lange brauchen, um eine ausreichend große Zahl in ihre Primfaktoren zu zerlegen. Eine 256-Bit Verschlüsselung, wie sie Finanzinstitute bei Kreditkartenzahlungen im Internet verwenden, gilt daher als kaum zu knacken und daher damit als ziemlich sicher. Sollte irgendjemand mal den Beweis antreten, dass NP doch gleich P sei, müssten sich die Banken schnell eine neue Methode einfallen lassen.

Seit Blums Paper veröffentlicht ist, zerbrechen sich weltweit Mathematiker und Informatiker den Kopf, ob der Bonner Forscher das Millenium-Problem tatsächlich gelöst hat. Nach ersten positiven Reaktionen, etwa vom Stanford-Mathematiker Reza Zadeh, tauchen nun die ersten Zweifel auf, ob Blums Beweisführung stimmig ist.

In einem Forum für theoretische Mathematik schreibt etwa der User Mikhail, er habe Alexander Razborov, auf dessen Arbeiten Blums Beweis beruht, zu Blums Arbeit befragt und dieser habe einen Fehler in Blums Paper gefunden: Blum widerspreche in einem zentralen Punkt seines Beweises, der Tardos-Funktion, einem seiner eigenen Annahmen, dem Theorem 6. Blums Beleg sei daher "notwendig falsch". Und der Mathematiker Scott Aaronson, der laut dem Standard so etwas wie eine Autorität in der NP-P-Frage ist, wettet auf seinem Blog sogar 200.000 Dollar darauf, dass Blums Beweis nicht standhalten wird.

"Bitte fragt mich nicht mehr weiter dazu", schreibt Aaronson. "Wenn das Ding am Ende der Woche nicht widerlegt ist, könnte ihr zurückkommen und mich einen ignoranten Idioten nennen."