Mathematik»Eine andere Welt«

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

Festplatte Computer Mathematik Rechner

Computer haben gewaltige Rechenkapazitäten – und doch braucht es für manche Matheaufgaben das menschliche Gehirn  |  © seraph/Photocase

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…

Anzeige

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…

Irit Dinur

Die Mathematikerin Irit Dinur ist Professorin für Informatik am Weizmann-Institut in Israel, an dem auch Nobelpreisträgerin Ada Yonath forscht. Dinurs Hauptforschungsgebiet ist die probabilistischen Überprüfung von Beweisen

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.

Schreiben Sie den ersten Kommentar!

    Bitte melden Sie sich an, um zu kommentieren

    • Artikel Auf einer Seite lesen
    • Schlagworte Mathematik | Affe | Computer
    Service