P/NP-Problem

Wer die Beschäftigung mit Arithmetik ablehnt, ist dazu verurteilt, Unsinn zu erzählen.

John McCarthy

Manche Probleme sind so unangenehm schwierig, dass es lohnt, sich gründlich zu überlegen, ob es überhaupt eine Lösung gibt oder ob man seine Zeit mit der Suche danach verschwendet. Für die sogenannten NP-Probleme gibt es zwar eine offensichtliche Lösung, aber bis man das Ergebnis kennt, ist einem der Bart durch den Tisch gewachsen. Leider interessieren sich enorm viele Menschen für die Ergebnisse dieser NP-Rechnungen. Sie sitzen in ihren Büros und kauen ungeduldig auf ihren Fingernägeln herum, während der Computer rechnet und rechnet. Ob es prinzipiell schnelle Lösungen für NP-Probleme gibt, das ist, grob gesagt, das sogenannte P/NP-Problem, eines der sieben mathematischen Rätsel, für deren Lösung das amerikanische Clay-Institut eine Million Dollar ausgesetzt hat. (Ein weiteres ist die →Riemann-Hypothese.) Die Lösung des P/NP-Problems würde zwar keineswegs bereits die schnelle Lösung für alle NP-Probleme der Welt mit sich bringen. Aber sie würde zeigen, ob es überhaupt Hoffnung gibt. Allerdings, so würden die meisten Experten heute sagen, sieht es eher düster aus.

Eines der bekanntesten NP-Probleme handelt von einem Händler, der mühselig durchs Land zieht, um seine Ware zu verkaufen. Die Frage ist, in welcher Reihenfolge er die Städte anfahren muss, um möglichst schnell fertig zu sein. In dieser Form ist das Problem heute allerdings gelöst: Der arme Mann erledigt seine Geschäfte einfach bei eBay. Stattdessen verreist man in der so gewonnenen Freizeit, um die Welt zu sehen. Man kauft den Reiseführer «999 Weltwunder, die man im Leben gesehen haben muss» und fährt los. Aber wo anfangen? In welcher Reihenfolge sollte man beim Abhaken der Sehenswürdigkeiten vorgehen, um nicht unterwegs zu sterben? Kann man das überhaupt alles bis zu seinem 80. Geburtstag schaffen? Und wird der Urlaub dann nicht entsetzlich stressig?

Ist man bescheiden und verlangt nur nach Eiffelturm, Big Ben, Forum Romanum und Vogelspark Walsrode, so lässt sich das Problem des verzweifelten Touristen leicht lösen: Man besorgt sich einen Routenplaner und rechnet die zurückzulegende Gesamtstrecke für alle möglichen Reihenfolgen der Orte aus. Man findet heraus, dass man eher nicht von Rom nach London, dann nach Paris und schließlich nach Walsrode fährt, sondern eine günstigere Reihenfolge wählen sollte. Kaum kommen jedoch ein paar Sehenswürdigkeiten hinzu, explodiert die Menge an Rechenarbeit. Bei fünf Orten gibt es schon 30 mögliche Reisewege, bei sechs 180, bei sieben 1260 und so weiter. Wenn man nur zehn verfallene Schlösser in Südfrankreich ansehen möchte, dann muss man bereits über drei Millionen Reisewege berechnen, um die kürzestmögliche Route zu bestimmen. Und um das Problem für alle 999 Sehenswürdigkeiten zu lösen, benötigt man, auch mit noch so schnellen Computern, deutlich mehr Zeit, als seit der Entstehung des Universums vergangen ist. Das verdirbt einem die ganze Vorfreude auf den Urlaub.

Auch wenn sich Generationen von klugen Menschen an dieser und ähnlich gelagerten Problemstellungen die Zähne ausgebissen haben: Es gibt bisher keine wesentlich schnellere Methode, um die beste Route für eine willkürliche Ansammlung von Reisezielen zu ermitteln, als gnadenlos alle Möglichkeiten durchzurechnen. Das Besondere an NP-Problemen wie dem vom verzweifelten Touristen ist nicht, dass sie komplizierte Rechnungen verlangen, im Gegenteil, einfaches Addieren von Zahlen reicht oft aus. Die Schwierigkeit liegt in der schieren Menge an Möglichkeiten, mit denen umzugehen ist. NP-Probleme sind die Marathonläufe unter den mathematischen Problemen – man muss lediglich laufen können, aber sehr, sehr weit.

Im Gegensatz dazu sind sogenannte P-Probleme nur wenige Stadionrunden lang und lassen sich meist mit überschaubarem Aufwand durchrechnen. Ein einfaches P-Problem ist zum Beispiel die Addition von Zahlen. Handelt es sich um fünf Zahlen, braucht man vier Rechenschritte, sind es tausend Zahlen, benötigt man 999. Allgemein benehmen P-Probleme sich anständig; wirft man ihnen größere Datenmengen vor, so sind sie nicht gleich beleidigt und ziehen sich für ein Weltalter zurück. Im Unterschied dazu steigt bei NP-Problemen die Zahl der Rechenschritte exponentiell mit der Menge der Daten an. Die entscheidende Frage ist nun: Sind NP-Probleme nebenbei auch P-Probleme? Vielleicht heimlich nachts unter der Bettdecke, wenn keiner hinsieht? Gibt es eventuell doch eine schnellere Lösung für die Reise des verzweifelten Touristen und für die vielen anderen langwierigen NP-Rätsel? Das ist, vereinfacht ausgedrückt, das P/NP-Problem, das so viele Menschen quält.

Und dabei handelt es sich nicht etwa nur um Mathematiker und Weltreisende. Überaus viele wichtige Probleme, über die Computer heutzutage in Unternehmen, Banken und Büros nachgrübeln, sind NP-Probleme und daher artverwandt mit dem Touristendilemma. Hätte man relativ schnelle Lösungen dafür, die hilfreichen Computer könnten herrliche Dinge ausrechnen. Wären NP-Probleme gleichzeitig P-Probleme und wüsste man daher sicher, dass es schnelle Lösungen gibt, würde das ungeahnte Energien bei der Suche nach diesen Lösungen freisetzen. Umgekehrt wäre vielen Experten wohler, wüssten sie sicher, dass NP nicht P ist. Das Entschlüsseln von Nachrichten ist beispielsweise in vielen Fällen auch ein NP-Problem, weswegen auch die Geheimhaltung von sorgsam gehüteten Informationen auf dem Spiel steht. Die Frage, ob NP gleich P ist oder doch nicht, ist daher bedeutend wichtiger als das leidige Problem der Schnürsenkel, die immer im unpassenden Moment aufgehen.

Um zu beweisen, dass NP-Probleme am Ende doch heimliche P-Probleme sind, würde es genügen zu zeigen, dass eines von ihnen eine schnelle, saubere Lösung hat. Das ist die Folge einer äußerst praktischen Eigenschaft von vielen wichtigen NP-Problemen: Hat man für eines von ihnen eine schnelle Lösung gefunden, bedeutet das, dass es für alle anderen NP-Probleme ebenfalls eine gibt, auch wenn man sie noch nicht kennt. Um zu zeigen, dass NP-Probleme garantiert nicht gleichzeitig P-Probleme sind, müsste man anders vorgehen: Man könnte zum Beispiel versuchen zu beweisen, dass sämtliche Lösungen für das Problem des verzweifelten Touristen sehr langwierig sind, und zwar nicht nur die, die man bisher ausprobiert hat, sondern auch alle, die man sich in Zukunft noch ausdenken wird. Wiederum würde es genügen, dies für ein bestimmtes NP-Problem zu zeigen. Wenn also zufällig ein Leser weiß, wie man das Problem des verzweifelten Touristen im Handumdrehen lösen kann, oder auch wenn er sicher weiß, dass es eine solche Lösung nicht gibt, so möge er das bitte nicht für sich behalten – es hat ungeahnte Folgen für nahezu alle wichtigen NP-Probleme, würde viele Menschen in Forschung und Wirtschaft in Aufregung versetzen und ihn zudem reich machen.

Und er möge sich bitte nicht davon entmutigen lassen, dass die meisten Experten es für unwahrscheinlich halten, dass P gleich NP ist. Für Mathematiker bedeutet Wahrscheinlichkeit gar nichts, erst ein definitiver Beweis lä st sie ruhig schlafen. Überhaupt sollte man nie annehmen, dass etwas nicht möglich ist, nur weil alle behaupten, es sei nicht möglich: Hätten wir vor wenigen hunderttausend Jahren einen Affen gefragt, ob seine Nachfahren je in der Lage sein werden, einen Elefanten umzubringen, hätte er uns vermutlich einen Vogel gezeigt. Und kaum vergingen einige Tage, schon stellt das gar keine Schwierigkeit mehr dar. So ähnlich könnte es uns auch mit den NP-Problemen gehen, vor denen wir heute stehen wie der Affe vor dem Elefanten.

Zur Beantwortung der P/NP-Frage benötigt man möglicherweise nicht einmal hochgradig komplizierte Mathematik – viele sagen, eine richtig gute Idee würde genügen. Darum ist die Zahl der Beweisvorschläge, die unter Hobbyproblemlösern kursieren, viel höher als bei den anderen Jahrtausendfragen der Mathematik. Was wir also brauchen, sind mehr intelligente Touristen, die ihre Urlaubsplanung richtig ernst nehmen.