Das Werkzeug ist weg – die Einsicht ist groß

Herr Professor Pokutta, Sie haben den Gödel-Preis dafür bekommen, dass Sie und ihre Kollegen zeigen konnten, dass das berühmte „Problem des Handlungsreisenden“ nicht effizient mit einem sogenannten linearen Programm gelöst werden kann. Was sind die Folgen dieser Erkenntnis?

Zunächst muss man vielleicht nochmal erklären, was das Problem des Handlungsreisenden ist. Es handelt sich dabei um ein kombinatorisches Optimierungsproblem: Die Aufgabe besteht darin, eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass keine Station außer der ersten mehr als einmal besucht wird, die gesamte Reisestrecke des Handlungsreisenden möglichst kurz und die erste Station gleich der letzten Station ist und diese wird nur zweimal insgesamt besucht.

Und dieses Problem lässt sich nun nicht effizient lösen?

Sie können es mit heutigen Computern in vertretbarer Zeit lösen für eine relativ geringe Anzahl von Orten. Aber mit steigender Anzahl von Orten wird das Problem exponentiell schwieriger zu lösen. Bei 15 Städten haben Sie schon 43 Milliarden mögliche Reiserouten, die Sie vergleichen müssen, und bei 18 Städten bereits über 177 Billionen. Es gibt für das Problem des Handlungsreisenden bestimmte Näherungslösungen. Uns hat aber ein anderer, fundamentaler Aspekt dieses Problems interessiert. Es geht dabei um die große Frage „P versus NP“.

Das ist eines der sogenannten Millenniumsprobleme, dem ihr Exzellenzcluster MATH+ im vergangenen Sommer sogar eine ganze Veranstaltung gewidmet hat.

Genau. Es gibt eine bestimmte Menge von Problemen, bei denen es leicht ist, die Korrektheit einer gefundenen Lösung zu überprüfen. Die Menge solcher Probleme nennen wir in der Komplexitätstheorie „NP“. Und dann gibt es noch eine Untermenge von NP, die nennen wir „P“. Das sind die Probleme, die sich leicht überprüfen lassen, und die dazu auch noch relativ leicht zu lösen sind. Die große Frage ist, sind die beiden Mengen vielleicht identisch? Sind alle Probleme, die sich einfach überprüfen lassen auch leicht zu lösen? Vielleicht haben wir einfach für die uns schwer erscheinenden Probleme in der Menge NP noch nicht den einfachen Lösungsweg gefunden, der sie dann auch zu Elementen von P machen würde. In dem Fall wäre P = NP.

War das Problem des Handlungsreisenden jetzt so ein Kandidat, bei dem man hätte zeigen können, dass P = NP ist?

Jein. Das Problem des Handlungsreisenden selber nennen wir NP-schwer. Es ist ja schwer zu überprüfen, ob eine gefundene Reiseroute tatsächlich die kürzeste ist. Uns ist keine deutlich bessere Lösung bekannt, als alle durchzuprobieren, und das wird eben schnell schwierig mit zunehmender Anzahl der Orte. Das Problem des Handlungsreisenden ist also gar kein Element der Menge NP. Aber es steht für eine ganze Klasse von ähnlichen Problemen, und darunter sind einige, die in NP liegen und mit denen ich prinzipiell P = NP zeigen könnte. Es ist nämlich so, dass ich im Prinzip nur für eines der momentan noch schwer zu lösenden Probleme in NP eine effiziente Lösung finden muss, um damit gleich für alle Probleme in NP einen effizienten Lösungsalgorithmus an der Hand zu haben. Deshalb gibt es viele, die solch eine effiziente Lösung suchen, um P = NP zu beweisen. Übrigens versuchen deutlich mehr Personen, das Gegenteil zu beweisen, nämlich dass P auf jeden Fall ungleich NP ist; dies wird auch hinlänglich als die korrekte Antwort vermutet.

Und diese Versuche sind nun alle sinnlos aufgrund ihrer Erkenntnisse?

Das nicht. Aber wir konnten zeigen, dass man auf alle Fälle die Methode der linearen Optimierung, die auch lineare Programmierung genannt wird, dafür nicht verwenden kann. Und gerade die galt eben bis 2012, als wir unsere Ergebnisse auf einer Konferenz vorgestellt haben, als einer der aussichtsreicheren Ansätze dafür.

Da werden ja einige Leute ganz schön enttäuscht gewesen sein …

Wir haben denen zumindest das Werkzeug weggenommen, das ist richtig. Aber es geht hier nicht um ein „ätsch, bätsch, ihr guckt jetzt in die Röhre“. Unser Beweis hat eine ganz wichtige, tiefgehende Erkenntnis geliefert. Nämlich, dass die lineare Programmierung keinen Universalalgorithmus darstellt, mit dem man im Prinzip Lösungen für jedes Problem suchen kann.

Dieses Wissen ist vermutlich auch extrem hilfreich, weil dadurch viel unnötige Arbeitszeit gespart wird. Überhaupt ist es in den Wissenschaften ja mittlerweile ein Trend, auch Negativ-Ergebnisse zu publizieren, um den Prozess des Erkenntnisgewinns effizienter zu machen.

Dass unser Beweis diese Effizienz erhöht, ist richtig. Bei den Negativ-Resultaten in der Mathematik geht es aber um etwas ganz anderes als etwa bei der Publikation eines naturwissenschaftlichen Experiments, das nicht geklappt hat. Dieses Wissen ist natürlich auch für die Kolleg*innen hilfreich. Aber Negativ-Beweise in der Mathematik sind Unmöglichkeitsresultate. Sie müssen ja zeigen, dass es wirklich für alle betrachteten Wege nicht funktioniert. Dagegen ist es oft leichter, einen Algorithmus zu finden, der funktioniert. An den wird auch gar kein Absolutheitsanspruch gestellt. Vielleicht kommt morgen eine Andere, die einen noch schnelleren Algorithmus findet.

Wie lange haben Sie und Ihre Kollegen denn dann an diesem kniffligen Negativ-Beweis gearbeitet?

Ungefähr sechs Monate.

Oh, das ging aber schnell!

Wir konnten auf Vorarbeiten von Mihalis Yannakakis von der Columbia University in New York aufbauen. Aber in der Mathematik korreliert die Schwierigkeit eines Problems nicht unbedingt mit der Zeit für das Finden der Lösung. Wenn Sie die richtige Idee haben, können Sie die Lösung oft sehr schnell ausarbeiten. Um diese Idee zu finden, können Sie nicht viel tun, außer die richtigen Leute zusammenzubringen und, ganz wichtig, Ruhe mitbringen, denn gute Ideen kommen nicht unter Zeitdruck und Stress. Dann kommt die richtige Idee manchmal schnell, manchmal dauert es Jahre. Oder sie kommt gar nicht. Das ist bisher bei sechs von sieben Millenniumsproblemen der Fall. Aber gerade das macht Mathematik ja so spannend.

Das Interview führte Wolfgang Richter.