Mathematik »Eine andere Welt«Seite 2/2

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