P vs. NP ist das bekannteste offene Problem der Theoretischen Informatik. Es fragt, ob sich jedes Problem, dessen Lösung man schnell prüfen kann, auch schnell lösen lässt. Für die Antwort – vermutlich Nein – schreibt das Clay Mathematics Institute eine Million US-Dollar aus (Millennium-Problem).
Die Klassen P und NP
P ist die Klasse der Entscheidungsprobleme, die ein Algorithmus in Polynomzeit löst – also praktisch effizient. NP umfasst die Probleme, deren Lösung sich in Polynomzeit verifizieren lässt, wenn man einen Kandidaten (einen „Zeugen") vorgelegt bekommt. Jedes P-Problem liegt trivialerweise in NP, also gilt P ⊆ NP. Die offene Frage ist, ob die Klassen gleich sind.
NP-vollständige Probleme
Die schwersten Probleme in NP heißen NP-vollständig: jedes andere NP-Problem lässt sich per Reduktion darauf zurückführen. Gäbe es für irgendein NP-vollständiges Problem einen Polynomzeit-Algorithmus, wäre P = NP – und alle NP-Probleme wären effizient lösbar. Paradebeispiele sind das Satisfiability-Problem (SAT), der Hamilton-Pfad und das Rucksackproblem.
Warum die Antwort wichtig ist
Verschlüsselung und digitale Signaturen bauen darauf auf, dass bestimmte Probleme (etwa Faktorisierung) praktisch schwer sind – bei P = NP wäre diese Grundlage hinfällig. Zugleich würden Optimierungsprobleme in Logistik, Planung und KI schlagartig exakt lösbar. Die Forschung umgeht die offene Frage mit Backtracking, Greedy-Heuristiken und Näherungsalgorithmen, die in der Praxis oft gute Lösungen liefern, obwohl der schlimmste Fall hart bleibt.
Stand der Forschung
Seit Jahrzehnten ist kein Beweis gelungen. Die überwältigende Mehrheit der Forscher vermutet P ≠ NP, unter anderem weil exponentielle Suchräume bei NP-vollständigen Problemen stabil wirken. Ein gängiger Beleg: Ohne Annahme P ≠ NP lassen sich viele scheinbar schwere Probleme nicht einmal relativ zu Orakeln trennen. Die formale Grundlage liefert die Aussagenlogik, in der SAT-Formeln als universelle Testobjekte dienen.