Informatik-Professor Norbert Blum

Professor zieht seinen Lösungsansatz zurück

Symbolbild: Der 63-jährige Bonner Informatik-Professor hat am 11. August einen 39-seitigen mathematischen Beweis ins Internet gestellt.

Symbolbild: Der 63-jährige Bonner Informatik-Professor hat am 11. August einen 39-seitigen mathematischen Beweis ins Internet gestellt.

Bonn. Der Bonner Informatik-Professor Norbert Blum veröffentlichte am 11. August einen Lösungsansatz für ein mathematisches Jahrhunderträtsel. Bei der Prüfung des Beweises fiel seinen Kollegen ein Fehler auf, daraufhin zog Blum den Ansatz zurück.

Zuweilen finden Menschen es chic, zu erzählen, dass für sie Zahlen und Mathematik „böhmische Dörfer“ seien. Erklärungen seien zwecklos, alles bleibe unverständlich. Und damit meinen manche Zeitgenossen sogar Dreisatz oder Prozentrechnung, die helfen, vermeintlich attraktive Rabattaktionen als betrügerische Luftnummern zu enttarnen.

Das liegt vielleicht auch daran, dass Schüler sich im Unterricht mit „Kurvendiskussion und dreidimensionaler Geometrie beschäftigen müssen und sich fragen: ,Wofür machen wir das denn hier?'“, hat Professor Ulrich Trottenberg, 20 Jahre Leiter des Fraunhofer-Instituts für Algorithmen und wissenschaftliches Rechnen in Sankt Augustin, mehr als einmal öffentlich zu Protokoll gegeben. Der Humboldt-Preisträger glaubt: Wenn die Lehrpläne sich etwa mit GPS-Navigation, mp3-Formaten oder dem Seiten-Ranking von Google und der dahinter steckenden Mathematik beschäftigen würden, dann wäre die deutsche Mathe-Aversion weniger ausgeprägt.

Sie ist auch deshalb schwer verständlich, weil alles, was der moderne Mensch in der Gegenwart schätzt, unsichtbar von Mathematik durchwoben ist. Wer hat heute – zum Beispiel – noch nicht gemailt, telefoniert, gegoogelt oder am Bankschalter Bares abgehoben? Auch Alfred Nobel, Stifter des weltweit prestigeträchtigsten Wissenschaftspreises, unterschätzte die Bedeutung der Mathematik und stufte sie als „Hilfswissenschaft“ ein. Seit 1901 werden Nobelpreise nur an Chemiker, Physiker, Mediziner, Literaten und Friedensstifter verliehen.

Nicht alle mathematischen Rätsel sind gelöst

Dass die Mathematik nicht dazu gehört, war nicht tragbar, weshalb die Internationale Mathematische Union (IMU) seit 1936 die Fields-Medaille verleiht. Jedoch nur alle vier Jahre und auch nur an Menschen, die nicht älter als 40 Jahre sind. Wahrscheinlich befürchtet man danach eine Art mathematische Menopause.

Bis heute bleiben letzte mathematische Rätsel. Eines heißt „Das P-NP-Problem“. Wochenlang war die internationale Fachwelt förmlich elektrisiert, auch die Bonner Universität. Das liegt an Norbert Blum. Der 63-jährige Bonner Informatik-Professor hat am 11. August einen 39-seitigen mathematischen Beweis ins Internet gestellt. Nachdem Kollegen diesen Beweis einer Überprüfung unterzogen, stießen sie auf einen Fehler. Daraufhin zog Norbert Blum am Mittwoch seinen Beweis vorerst zurück. Auf der Wissenschaftsplattform Arxiv schrieb der Professor: "Der Beweis ist falsch. Ich werde genaustens prüfen, wo der Fehler liegt. Um dies zu tun, brauche ich etwas Zeit. Die Erklärung werde ich auf meine Homepage laden."

Alle zuvor waren gescheitert

Er hat ja zunächst auch nicht behauptet, ein Welträtsel gelöst zu haben, sondern lediglich einen Stein – „Prüft das mal“ – ins Wasser geworfen. Reaktionen ließen nicht lange auf sich warten.

Reza Zadeh, Professor für Künstliche Intelligenz an der renommierten Stanford-Universität (USA), twitterte: „Hat jemand bis jetzt einen Fehler in dem P-NP-Beweis gefunden? Norberts vorherige Arbeit ist großartig gewesen.“ Scott Aaronson, Physiker, Professor für Computerwissenschaft am renommierten Massachusetts Institute of Technology (MIT) und eine Art Guru beim P-NP-Problem, wettet 200 000 Dollar darauf, dass Blums Beweis einen Fehler enthält. So hat Aaronson auch schon vor sechs Jahren gewettet – und recht behalten. 2010 war der indische Hewlett-Packard-Experte Vinay Deolalikar ebenfalls an die P-NP-Prüffront gezogen. Wie 115 andere zuvor auch. Alle waren gescheitert.

Dabei hört sich „Prüffront“ kolossal mächtig an, tatsächlich hatte Deolalikar nur 21 Mathematiker – weltweit – für ausreichend kompetent befunden, einen solchen Beweis überhaupt prüfen zu können. Das spiegelt, in welch unterschiedlichen Mathe-Welten die letzten Rätsel beheimatet sind.

Lösung wäre alltagsrelevant

Wie sicher ist die Kreditkartennummern-Verschlüsselung? Die Antwort gibt möglicherweise die Lösung eines der sieben Welträtsel.

Wie sicher ist die Kreditkartennummern-Verschlüsselung? Die Antwort gibt möglicherweise die Lösung eines der sieben Welträtsel.

 

Das P-NP-Problem unterscheidet sich insofern von anderen, als dass seine Lösung alltagsrelevant wäre. Vereinfacht unterscheiden Mathematiker Probleme, die absehbar mit einem vertretbaren Rechenaufwand gelöst werden können von solchen, wo der Computer nie aufhört zu rechnen. Es gibt somit einfache Probleme (P) und „dicke Bretter“ (NP). Anschaulich lässt sich das am Dilemma eines Handlungsreisenden illustrieren, der viele Städte besucht, oder eines Müllfahrers, der in Straßen die Abfalltonnen leert. Wie lässt sich die schnellste und damit preisgünstigste Route bestimmen?

Bei drei Städten hilft dem Handlungsreisenden noch die „Pi-mal-Daumen“-Methode. Kämen noch zwei, drei Städte hinzu, hilft das Tom-Tom-Navi und findet jeweils die kürzeste Strecke von A nach B und weiter nach C, D und E, aber nicht die kürzeste Gesamtstrecke. Sind es bei fünf Städten 24 Möglichkeiten, um das Optimum herauszufiltern, explodiert danach die Zahl der zu prüfenden Varianten.

Die Zahl der Rechenschritte wächst exponentiell: Sind es bei sechs Städten noch 120 Varianten, sind es bei acht Städten schon 5040, bei 15 Städten gar 87 Milliarden Varianten – und ein Computer, so heißt es, wäre für eine 100-Städte-Optimalroute, wenn er jede Variante vollständig berechnet, länger unterwegs als das Universum alt ist. Fazit: Steigt der Daten-Input, wächst die Komplexität und ergibt sich eine nicht berechenbare NP-Aufgabe. Eine solche findet sich in der modernen Welt an jeder Ecke: Telekommunikation, Speicherchips oder bei weiter zu optimierenden Abläufen in Produktion, Transport oder Verkehr.

Algorithmen sind nützliche Helfer

Auch Algorithmen, die Google, Facebook, Amazon & Co. immer mehr Daten von internetaktiven Personen zusammenführen und Zusammenhänge („Das könnte auch Sie interessieren“) produzieren lässt, helfen bei NP-Problemen nicht, haben aber das öffentliche Interesse für Algorithmen gesteigert: Was für mysteriöse Formeln spielen da im Hintergrund? Reine, wertfreie Mathematik!

Algorithmen sind nützliche mathematische Helfer bei P-Problemen, verkürzen Rechenwege, machen den Computer effizienter und schneller. Auch ein simples Kochrezept ist letztlich ein Algorithmus: Eine Handlungsanweisung, die mit einer vorgegebenen endlichen Zahl einzelner Schritte zu einem Ergebnis kommt. Mathematisch anspruchsvoller ist ein Algorithmus, der – zum Beispiel – aus einem digitalisierten Musikstück die (für einen Menschen) nicht hörbaren Töne herausfiltern soll, um Speicherplatz zu sparen. Fertig ist das mp3-Format. Und es klingt für Menschen weiter wie das Original.

Die große Frage ist nun: Spielen NP-Probleme im Grunde auch nur in der P-Liga, und war bisher bloß noch niemand schlau genug, sie über einen effektiven Algorithmus rechenbar zu machen? Oder spiegeln P- und NP-Probleme völlig unvereinbare Welten? Kurzum: Ist P ≠ NP oder P = NP?

NP-Probleme verweigern sich P-Lösungen

Siegt die Unvereinbarkeit, könnten Banker jedenfalls ruhiger schlafen. Dazu ein Beispiel: 72 ist 9 mal 8; das weiß jeder aus dem Matheunterricht. Aber bei 184.626 wird es schon schwieriger, die Teiler 234 und 789 zu finden. Und wenn eine Zahl aus mehr als 100 Ziffern besteht, beginnt die Aussichtslosigkeit. Deshalb fühlen sich die Kryptografen auch sicher, denn sie verschlüsseln Kreditkartennummern, die Menschen immer häufiger für einen Internet-Zahlvorgang auf ihrer Tastatur eintippen, mit Zahlen aus 256 Ziffern. Wäre hingegen NP gleich P, wäre das – aus Bankensicht – ein Katastrophen-Szenario. Geheimdienste würden hingegen Aufbruchstimmung empfinden.

Einstweilen ist aber nichts bewiesen. Im mathematischen Alltag gilt indes (noch) die Annahme: NP-Probleme sind eine eigene mathematische Spezies und verweigern sich P-Lösungen. Die Logik-Akrobaten auf dem Hochreck, eher für Präzision und Falsch-oder-Richtig-Lösungen bekannt, sind jedoch nicht instinktlos. Vor 15 Jahren gab es dazu eine Umfrage: Das „mathematische Bauchgefühl“ ließ 61 von 100 Spezialisten ihr Kreuz bei „P ungleich NP“ machen. Auch der Bonner Blum kommt in seiner Beweisführung zu diesem vorläufigen und für Banken beruhigenden Ergebnis. Vielleicht wird eines Tages aber auch ein Beweis der dritten Art präsentiert, wie ihn der Berliner Mathematiker und Leibniz-Preisträger Günter Ziegler für möglich hält: „Das P-NP-Problem ist beweisbar unbeweisbar.“ „Das ist auch meine Meinung“, sagt der Bonner Mathematiker Korte.

Ob es für einen solchen Beweis das Preisgeld von einer Million Dollar gäbe, ist eine andere Frage. Seit dem Jahr 2000 hat das Clay Mathematics Institute (CMI) in Cambridge (Massachusetts/USA) diesen Köder ausgelegt und die sieben mathematischen Welträtsel benannt, die sogenannten Millenniums-Probleme. Das P-NP-Problem gehört dazu. Seit 2010 steht fest, dass der erste und bisher einzige Rätsellöser, Grigori Jakowlewitsch Perelman, das Preisgeld gar nicht abgeholt hat.

Beweisprüfung dauerte vier Jahre

Der Russe hatte seinen Beweis für die 100 Jahre alte Poincaré-Vermutung bereits 2002 im Internet veröffentlicht. Vier Jahre dauerte die Beweisprüfung – „intrigenreiche Jahre“, sagte Professor Sergej Rukshin, Perelmans mathematischer Ziehvater, einmal dem Wirtschaftsmagazin „brandeins“. Perelman habe Grund, „das internationale mathematische Establishment zu verachten“. Am Ende dann doch grünes Licht für Perelman. Vereinfacht bedeutet sein Denkergebnis, dass das Universum die Form eines Autoreifens, einer Kugel oder einer Brezel haben könnte; es könnte endlich sein, obwohl es dem Menschen unendlich groß erscheint – wie ein Autoreifen einer auf ihm krabbelnden Ameise.

2006 zeichnete die IMU in Madrid Perelman mit der Fields-Medaille aus, aber der erschien nicht. Im selben Jahr ernannte die Redaktion des US-Fachblatts „Science“ die Denkleistung des Russen zum wichtigsten Wissenschaftserfolg des Jahres. 2010 gab das Clay-Institut schließlich die Million frei, aber der mittellose Perelman, der bei seiner Mutter in der siechen Plattensiedlung Kuptschino am Stadtrand von Sankt Petersburg lebt, verzichtete. Ebenso auf angebotene Professuren aus seinem Heimatland, aber auch aus den US-Tempeln Stanford und Princeton. Perelman, inzwischen 51, gilt als großer Schweiger „mit eigener Psychologie“, wie der damalige IMU-Präsident John Ball preisgab. Und: „Perelman fühlt sich von der internationalen mathematischen Gemeinschaft isoliert“, deshalb wolle er ihr auch nicht als „Aushängeschild“ dienen.

Dem Magazin „The New Yorker“ vertraute er einmal an, es würden von der mathematischen Gemeinschaft nicht jene geächtet, die kein Ethos hätten und Plagiate in die Welt setzten, sondern „es sind Leute wie ich, die isoliert sind“. Gemeint waren jene beiden Chinesen, die Perelmans Beweis ein neues Outfit gaben und ihn als eigenen im „Asian Journal of Mathematics“ veröffentlichten. Rukshin glaubt, Perelman scheitere an einer Art moralischem Maximalismus und sei „zu ehrlich, um heute zu leben“. In Russland nennen sie Perelman einen „weißen Raben“.