P gegen NP
P gegen NP ist die berühmteste offene Frage der Informatik: Ist jedes Problem, dessen Lösung sich schnell überprüfen lässt, auch schnell lösbar? Niemand weiß es, und auf die Antwort ist eine Million Dollar Preisgeld ausgesetzt.
Manche Aufgaben sind schwer zu lösen, aber leicht zu kontrollieren. Ein Sudoku auszufüllen kann Stunden dauern. Ein ausgefülltes Sudoku zu prüfen dauert eine Minute. Genau diese Lücke ist der Kern der Frage P gegen NP. P steht dabei für die Aufgaben, die ein Computer schnell selbst lösen kann. NP steht für die Aufgaben, bei denen er eine fertige Lösung wenigstens schnell nachprüfen kann. Die offene Frage lautet: Sind das in Wahrheit dieselben Aufgaben? Seit über fünfzig Jahren hat das niemand beweisen oder widerlegen können.
Was an dieser einen Frage hängt
Das Clay Mathematics Institute hat die Frage im Jahr 2000 zu einem der sieben Millennium-Probleme erklärt. Auf einen Beweis stehen eine Million US-Dollar. Doch das Geld ist der kleinste Teil der Bedeutung. Praktisch die gesamte digitale Sicherheit beruht auf der stillen Annahme, dass P und NP nicht dasselbe sind.
Wenn du im Browser eine verschlüsselte Verbindung aufbaust, wird oft mit sehr großen Zahlen gerechnet. Die Sicherheit beruht darauf, dass niemand diese Zahlen schnell in ihre Faktoren zerlegen kann. Das Prüfen ist dagegen trivial: man multipliziert die Faktoren und schaut, ob es passt. Wäre P gleich NP, gäbe es womöglich ein schnelles Verfahren zum Knacken. Onlinebanking, Passwörter und digitale Signaturen müssten neu gedacht werden.
Die andere Seite wäre allerdings ein Segen. Viele wichtige Optimierungsaufgaben gehören zu NP: Stundenpläne, Routenplanung für Lieferflotten, Faltung von Proteinen in der Medikamentenforschung. Ein schnelles Allzweckverfahren würde diese Probleme auf einen Schlag lösbar machen. Die meisten Fachleute halten das aber für unwahrscheinlich. In Umfragen unter Forschenden tippt eine große Mehrheit darauf, dass P und NP verschieden sind.
Schnell lösen gegen schnell prüfen
« Schnell » hat hier eine feste Bedeutung. Informatiker schauen, wie stark die Rechenzeit wächst, wenn die Aufgabe größer wird. Wächst sie höchstens wie eine Potenz der Eingabegröße, gilt das als schnell. Man nennt das Polynomialzeit, und daher kommt das P. Wächst die Zeit dagegen mit jedem zusätzlichen Element ums Doppelte, ist die Aufgabe schon bei mittleren Größen praktisch unlösbar.
NP umfasst alle Aufgaben, bei denen sich ein vorgeschlagener Lösungsvorschlag in Polynomialzeit prüfen lässt. Jedes Problem aus P steckt automatisch auch in NP, denn wer selbst schnell rechnen kann, kann erst recht schnell kontrollieren. Die Frage ist nur, ob es in NP zusätzlich Aufgaben gibt, die dort nicht auch schon herausfallen.
Ein Werkzeug macht die Sache handhabbar: die NP-vollständigen Probleme. Das sind die härtesten Fälle in NP, und sie lassen sich alle ineinander übersetzen. Findet jemand für ein einziges davon ein schnelles Verfahren, fallen alle anderen mit um. Zu dieser Gruppe gehören das Rundreiseproblem eines Handlungsreisenden und viele Rätsel wie Sudoku in verallgemeinerter Form. Dass trotz jahrzehntelanger Suche für keines ein schnelles Verfahren gefunden wurde, ist das stärkste Indiz gegen P gleich NP. Ein Beweis ist es nicht.
Wo dir das Problem im Alltag über den Weg läuft
Der häufigste Kontakt läuft über Verschlüsselung. Jedes Schloss-Symbol in der Adressleiste des Browsers steht für ein Verfahren, das auf schwer umkehrbaren Rechnungen beruht. Auch in der Debatte um Quantencomputer taucht das Thema auf. Wichtig ist dabei eine Abgrenzung: Quantencomputer würden P gegen NP nicht auflösen. Sie sind bei bestimmten Spezialaufgaben schneller, etwa beim Zerlegen großer Zahlen, aber niemand erwartet, dass sie alle NP-Probleme knacken.
In der Software-Praxis stößt man laufend auf NP-vollständige Aufgaben, ohne dass jemand den Begriff nennt. Ein Lieferdienst, der Touren plant, sucht keine perfekte Route. Er nimmt eine gute Näherung, die in Sekunden fertig ist. Genau so arbeiten auch Planungswerkzeuge für Schulstundenpläne oder Chip-Layouts. Der Verzicht auf die optimale Lösung ist eine direkte Folge dieser Theorie.
In Nachrichten taucht der Begriff auf, wenn jemand einen Beweis ankündigt. Das passiert regelmäßig, und bisher hielt keiner der Versuche einer Prüfung stand. Ein verbreiteter Irrtum ist außerdem, KI könne die Frage einfach umgehen. Ein Sprachmodell rät nur gute Kandidaten. Es verwandelt eine schwere Aufgabe nicht in eine leichte.