Mathematik »Eine andere Welt«

Mathematiker streiten über Probleme, die jeden Computer überfordern.

© seraph/Photocase

Computer haben gewaltige Rechenkapazitäten – und doch braucht es für manche Matheaufgaben das menschliche Gehirn

DIE ZEIT: Hier in der indischen Stadt Hyderabad treffen die Mathematiker gerade zu ihrem Weltkongress zusammen. Im Vorfeld machte ein Beweis Furore , der zeigen sollte, dass P ungleich NP ist. Was bedeutet das, »P≠NP«?

Irit Dinur: P ist die Klasse der Probleme, für die wir einen effizienten Lösungsweg haben. NP ist die Klasse der Probleme, für die wir zwar keinen Weg kennen, aber deren konkrete Lösungen wir durchaus effizient überprüfen können…

ZEIT: …so wie das Problem des Handlungsreisenden, der auf kürzester Gesamtstrecke eine Anzahl von Städten besuchen soll. Es gibt bis heute keinen Rechenweg dafür…

Dinur: Genau. Aber wenn uns jemand eine Route gibt, können wir immerhin effizient überprüfen, ob diese korrekt ist.

ZEIT: Was heißt hier Effizienz?

Dinur: Die messen wir an der Rechenzeit. Es gibt ein paar harmlos aussehende Probleme, für deren Lösung man mehr Schritte braucht, als das Universum Atome hat. Ein Computer würde bis ans Ende der Zeit daran rechnen.

ZEIT: Aber Computer werden doch jedes Jahr besser.

Dinur: Dann machen wir die Aufgabe eben komplexer, und der Fortschritt ist wieder aufgezehrt. Das ist ein prinzipielles Problem.

ZEIT: Wir haben also einerseits P und andererseits NP…

Dinur: Und unter den NP-Problemen gibt es einige, die ganz unschuldig wirken, aber universell sind, weil sie alle anderen Probleme beinhalten. Die nennt man »NP-vollständig«, etwa die 3-Färbung eines Graphen. Könnte man zeigen, dass eines dieser universellen Probleme nicht zu P gehört, dann wäre P≠NP bewiesen.

ZEIT: Was aber, wenn P doch gleich NP wäre?

Dinur: Dann hätten wir eine sehr interessante Welt. Das würde bedeuten, dass man alles, was man überprüfen kann, auch erschaffen könnte: Ich bewundere ein Gemälde, überprüfe quasi seine Schönheit, könnte es also ebenso selbst malen.

ZEIT: Demnach würden alle Künstler und alle Mathematiker arbeitslos?

Dinur: Einen mathematischen Satz zu beweisen wäre nichts Besonderes mehr, nur noch ein sturer Automatismus. Die menschliche Fantasie, die in der Entdeckung eines Beweises steckt, wäre überflüssig. Darum glauben die meisten Mathematiker und Informatiker nicht an P=NP. Wir sind überzeugt, dass man andere Fähigkeiten braucht, um Kunst, Musik oder eben elegante Mathematik zu erschaffen, als sie nur nachzuvollziehen.

ZEIT: P≠NP ist eines der sieben Millenniumsprobleme, für deren Lösung je eine Million Dollar ausgesetzt ist. Vor zwei Wochen hat Vinay Deolalikar einen 100-seitigen Beweis präsentiert. Als sich den eine Handvoll Leute anschauten, fanden sie recht schnell Fehler. Seit 1971 wird daran geforscht. Ist P≠NP mit den aktuellen Mitteln der Mathematik überhaupt zu fassen?

Dinur: Es ist das wichtigste Problem der Theoretischen Informatik. Viele Menschen arbeiten daran, aber es ist keine Sache, die in den nächsten ein oder zwei Jahren erledigt wird. Schon von einer Menge leichterer Fragen wissen wir nicht einmal, wie wir sie lösen könnten.

ZEIT: Mit der Poincaré-Vermutung – dem ersten Millenniumsproblem, das gelöst wurde – hat sich ein Einsiedler mehrere Jahre in seiner Kammer verschanzt und dann alle Welt mit dem Beweis überrascht. Kann das wieder passieren?

Dinur: Ich glaube, das ist nicht sehr wahrscheinlich. Manche Leute halten P≠NP für das schwerste Millenniumsproblem.

ZEIT: Könnte es auch schlicht unlösbar sein?

Dinur: Es ist wahr oder nicht – entweder gibt es einen Algorithmus oder nicht. Es ist jedoch möglich, dass es uns nie gelingt, seine Korrektheit zu beweisen.

ZEIT: Sie haben hier in Hyderabad einen viel beachteten Vortrag zur »probabilistischen Überprüfung von Beweisen« gehalten. Was dürfen sich Laien darunter vorstellen?

Dinur: Bei mathematischen Beweisen denkt man zunächst an eine Folge von Sätzen, einer aus dem anderen abgeleitet, die schließlich zu dem behaupteten Satz führen. Wenn da mittendrin irgendwo ein Fehler steckt, dann kann es noch so schön weitergehen, der Beweis bleibt falsch. An diese Empfindlichkeit gegenüber kleinen Fehlern haben wir uns gewöhnt. In meinem Arbeitsgebiet zeigen wir einen Weg auf, wie man Beweise in eine formale Sprache übersetzt, sodass, falls der Beweis falsch ist, es überall kleine Fehler gibt. Man kann ihn dann schon entlarven, indem man nur einen kleinen Ausschnitt überprüft. Das ist wie wenn man einen kleinen Klecks Marmelade auf einer Scheibe Toast hat – wir verteilen ihn über das ganze Brot, sodass man nur einen Bissen nehmen muss, um mit hoher Wahrscheinlichkeit zu wissen, ob Marmelade drauf ist oder nicht.

ZEIT: Geben sich denn Mathematiker zufrieden mit der Aussage »dieser Beweis ist mit 99-prozentiger Wahrscheinlichkeit korrekt«?

Dinur: Wenn ihnen das nicht reicht, können wir die Zahl problemlos auf 99,99 Prozent erhöhen. Das ist ziemlich gut, verglichen mit der menschlichen Fehlerquote bei der Überprüfung eines konventionellen Beweises.

ZEIT: Könnte man mit Ihrer Methode auch den Beweis von Vinay Deolalikar überprüfen?

Dinur: Nein, wir benutzen sie nur für Fälle wie die knappe Behauptung, dass es eine 3-Färbung für einen Graphen gibt. Es ist sehr schwer, einen mathematischen Beweis formal aufzuschreiben, meist wird doch eine Menge Umgangssprache darin verwendet.

ZEIT: Aber im Fall des Graphen gäbe es doch auch einen trivialen Weg – man überprüft einfach alle möglichen Färbungen und schaut jedes Mal, ob es eine Kante mit gleichfarbigen Endpunkten gibt. Ein richtiger mathematischer Beweis hat doch keine solche triviale Lösung!

Dinur: Das stimmt nicht. Sehen Sie das mal so: Jeder Beweis hat einen maximalen Umfang – selbst wenn es 100 Millionen Seiten sind. Theoretisch könnte man alle Buchstabenkombinationen untersuchen, die einen Text von 100 Millionen Seiten ergeben, und eine nach der anderen daraufhin überprüfen, ob sie einen gültigen Beweis darstellt. Wie der Affe an der Schreibmaschine, der irgendwann zufällig einen Shakespeare-Text schreiben wird! Das ist auch nur eine Frage der Rechenzeit, und für große Graphen braucht man ähnlich viel.

ZEIT: Womit wir zur Frage der Effizienz zurückkommen…

Dinur: Rechenzeit ist immer auch ein Maß für Verständnis. Wer nur alle Möglichkeiten stur durchrechnet, hat ein Problem nicht wirklich verstanden. Wenn man etwas hingegen effizient tut, dann erfasst man etwas von der wirklichen Struktur seines Gegenstandes.

ZEIT: Also geht es bei P≠NP eigentlich gar nicht um Computer?

Dinur: Richtig, das geht viel tiefer. Wenn P wirklich gleich NP wäre, dann ließen sich viele schwierige Probleme plötzlich ganz leicht lösen. Und daran glaube ich einfach nicht.

Das Gespräch führte Christoph Drösser