Homers letzter Satz: Die Simpsons und die Mathematik (German Edition)

ein codierter Hinweis auf Pacific Data Images, den Produzenten der Computergrafik in diesen Szenen. Auf dem Tastenfeld eines Telefons stehen diese Zahlen für die Buchstaben P, D und I.
    Als drittes ist kurz eine kosmologische Gleichung (ρ m 0 > 3 H 0 2 /8π G ) zu sehen, welche die Dichte von Homers Universum beschreibt. Die Gleichung war ein Beitrag des Astronomen David Schiminovich, einem alten Freund Cohens. Sie steht für eine hohe Dichte, sodass die entstehende Massenanziehung Homers Universum irgendwann kollabieren lässt. Und genau das geschieht auch am Ende der Geschichte.
    Kurz bevor Homers Universum sich auflöst, hält Cohen dem aufmerksamen Zuschauer einen besonders ansprechenden mathematischen Leckerbissen vor die Nase. In dem Bild auf Seite 201 ist eine ungewöhnliche Version der Euler’schen Formel über Homers linker Schulter zu sehen. Auch in »The Lisa Series« taucht diese Formel auf.
    Im selben Bild ist außerdem die Beziehung P = NP über Homers rechter Schulter zu erkennen. Den meisten Zuschauern wären diese drei Buchstaben kaum aufgefallen, und noch weniger hätten sich Gedanken darüber gemacht. Doch P = NP trifft eine Aussage über eines der wichtigsten ungelösten Rätsel der theoretischen Informatik.
    P = NP ist eine Aussage über zwei Klassen mathematischer Probleme. P steht für polynomial , NP für nichtdeterministisch polynomial. Stark vereinfacht ausgedrückt lassen sich Probleme der Klasse P einfach lösen, während Probleme der Klasse NP schwer zu lösen, aber einfach zu überprüfen sind.
    Multiplikation ist zum Beispiel einfach und wird daher zu den Problemen der Klasse P gezählt. Selbst wenn die zu multiplizierenden Zahlen größer werden, erhöht sich der Zeitaufwand für die Berechnung nur relativ schwach.
    Die Faktorisierung dagegen ist ein Problem der Klasse NP. Bei der Faktorisierung einer Zahl sucht man einfach nach ihren Teilern. Ein triviales Problem bei kleinen Zahlen, aber für sehr große Zahlen wird es schnell extrem aufwendig. Wenn man die Zahl 21 faktorisieren wollte, wäre die Antwort offensichtlich: 21 = 3 × 7. Bei der Zahl 428783 wäre das deutlich schwieriger. Mit einem Taschenrechner kann es gut eine Stunde dauern, bis man herausfindet, dass 428783 = 521 × 823. Wenn man jedoch die Zahlen 521 und 823 auf einem Zettel ausgehändigt bekäme, hätte man nach wenigen Sekunden bestätigt, dass es sich dabei um die korrekten Teiler handelt. Faktorisierung ist damit ein klassisches Problem der Klasse NP: schwer lösbar für sehr große Zahlen, aber leicht zu überprüfen.
    Oder … ist die Faktorisierung vielleicht gar nicht so schwer, wie wir derzeit glauben?
    Die entscheidende Frage für Mathematiker und Informatiker ist, ob die Faktorisierung wirklich schwer zu erreichen ist oder ob einfach nur noch niemand einen Trick gefunden hat, der sie einfach machen würde. Dasselbe gilt für zahlreiche andere Probleme, die derzeit zur Klasse NP gerechnet werden. Sind sie alle wirklich schwer lösbar, oder sind sie nur schwierig, weil wir zu dumm sind, einen einfachen Lösungsweg zu finden?
    Die Beantwortung dieser Frage ist nicht nur von akademischem Interesse, weil wichtige Technologien, etwa in der Verschlüsselung, nur funktionieren, wenn NP-Probleme praktisch unlösbar sind. Einige weit verbreitete Verschlüsselungsalgorithmen basieren auf der Annahme, dass große Zahlen schwer zu faktorisieren sind. Wenn die Faktorisierung aber nicht inhärent schwierig wäre und jemand einen Trick fände, der Faktorisierung einfach macht, wären diese Verschlüsselungssysteme unbrauchbar, mit dem Ergebnis, dass die Sicherheit in allen Bereichen in Gefahr wäre, von privaten Online-Einkäufen bis zu internationaler politischer und militärischer Kommunikation der höchsten Sicherheitsstufe.
    Das Problem wird oft zusammengefasst als »P = NP oder P ≠ NP?« und führt zu der Frage, ob es eines Tages möglich sein wird zu zeigen, dass augenscheinlich schwierige Probleme (NP) genauso einfach zu lösen sind wie simple Probleme (P).
    Die Suche nach einer Lösung für die Frage »P = NP oder P ≠ NP?« steht bei Mathematikern ganz oben auf der Liste der zu lösenden Rätsel. Es wurde sogar ein Preisgeld dafür ausgesetzt. Das Rätsel ist eines von sieben Jahrtausendproblemen, die das Clay Mathematics Institute, das der Philanthrop Landon Clay in Cambridge/Massachusetts (USA) gründete, im Jahr 2000 ausschrieb. Wer die endgültige Antwort auf die Frage »P = NP oder P ≠ NP?« findet,