Lexikon des Unwissens: Worauf es bisher keine Antwort gibt (E-Book zu Print) (German Edition)

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