Die Zeit
Mathematiker streiten über Probleme, die jeden Computer überfordern.
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“?
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.
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.
Dinur: Dann machen wir die Aufgabe eben komplexer, und der Fortschritt ist wieder aufgezehrt. Das ist ein prinzipielles Problem …