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

Beispiel kollidiert Afrika mit Europa, ein Vorgang, der schon die Alpen und die Pyrenäen erzeugt hat und bereits in 50 Millionen Jahren dazu führen könnte, dass das Mittelmeer mit Sand aus der Sahara zugeschüttet wird. Und in manchen Szenarien würde in nur 250 Millionen Jahren Amerika zur Kontinentversammlung aus Europa, Asien und Afrika hinzustoßen. Wir wissen nicht so genau, ob es in Westafrika oder Ostasien andocken wird. Ob New York also in der näheren geologischen Zukunft neben Namibia liegt oder eher San Francisco in Japan, ist ungewiss. Aber auf diese Weise entstünde schon praktisch übermorgen ein neuer Superkontinent, der, je nachdem, wie er am Ende aussieht, Amasia oder (wenig kreativ) Pangäa Ultima heißen könnte. Zum Glück ist noch genug Zeit, um sich einen originelleren Namen auszudenken.

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