Im Jahr 1971 veröffentlichte Stephen Cook an der University of Toronto The Complexity of Theorem-Proving Procedures und definierte eine Klasse — NP-vollständig —, deren Mitglieder in einem präzisen Sinn alle gleich schwer sind. Richard Karp aus Berkeley legte 1972 mit einundzwanzig solchen Problemen nach — Graphenfärbung, Travelling Salesman, Erfüllbarkeit, Rucksack —, alle wechselseitig aufeinander reduzierbar, und die daraus hervorgehende Frage P gegen NP (lässt sich jedes Problem, dessen Lösung schnell prüfbar ist, auch schnell lösen?) wurde zur größten offenen Frage der Informatik. Das Clay Mathematics Institute setzte sie 2000 auf die Liste seiner sieben Millennium-Preis-Probleme mit einer Million Dollar Preisgeld, das bis heute unangefasst ist. Die meisten Forscher glauben, P ≠ NP; bewiesen hat es niemand.
P umfasst die Probleme, die sich in polynomieller Zeit lösen lassen — Sortieren, kürzeste Wege, lineare Programmierung sitzen bequem darin. NP umfasst jene, deren vorgeschlagene Lösungen sich in polynomieller Zeit prüfen lassen — Sudoku ist das Haushaltsbeispiel: lösen schwer, prüfen trivial. NP-vollständige Probleme sind die schwersten in NP: jedes NP-Problem reduziert sich in polynomieller Zeit auf jedes NP-vollständige, ein schneller Algorithmus für eines ergäbe also schnelle Algorithmen für alle. Cooks Ergebnis von 1971 war, dass die boolesche Erfüllbarkeit NP-vollständig ist; Karp dehnte den Beweis im Folgejahr auf Dutzende natürlicher Probleme aus. Wäre P = NP, läge jedes NP-vollständige Problem in P, und die Folgen wären enorm — die Kryptografie bräche, die Optimierung (Logistik, Scheduling, Wirkstoffdesign) würde handhabbar, suchbasierte KI-Systeme würden ungeheuer mächtiger. Gilt hingegen P ≠ NP, die augenscheinliche Wirklichkeit, klafft eine fundamentale Lücke zwischen Prüfen und Finden. Aus drei Richtungen läuft der Glaube an P ≠ NP zusammen: Jahrzehnte intensiver Erfolglosigkeit bei der Suche nach polynomiellen Algorithmen für SAT oder TSP; formale Resultate, die zeigen, dass die heutigen Beweistechniken (Relativierung, natürliche Beweise, Algebrisierung — Razborov-Rudich, Aaronson-Wigderson) die Frage gar nicht entscheiden können; und der praktische Befund, dass moderne Kryptografie darauf ruht, dass bestimmte Probleme schwer bleiben. Mehrere Ausgänge sind weiterhin denkbar: ein P = NP mit kleinen Konstanten wäre eine praktische Revolution; ein galaktischer Algorithmus (Liptons Wort) in polynomieller Zeit mit astronomischen Konstanten wäre theoretisch interessant, praktisch belanglos; und einige Forscher (Aaronson) nehmen die gödelartige Möglichkeit ernst, dass die Frage von der Standardmathematik unabhängig ist.
P gegen NP ist der unausgesprochene Angelpunkt heutiger Technologie: die Verschlüsselung jeder Banktransaktion, jeder HTTPS-Verbindung, jedes sicheren Messengers ruht darauf, dass als schwer geglaubte Probleme (Faktorisierung, diskreter Logarithmus, Gitterprobleme) tatsächlich schwer sind, und die Optimierungsprobleme von Logistikern, Fluggesellschaften, Chipdesignern und Pharmafirmen sind in der Praxis NP-schwer — gelöst wird mit Heuristiken (Simulated Annealing, genetische Algorithmen, Branch-and-Bound, zunehmend gelernte RL-Heuristiken), die ohne beweisbare polynomielle Garantien gut genug arbeiten. Ein hinreichend großer Quantencomputer würde nicht alle NP-Probleme effizient lösen — die Klasse BQP enthält NP nach gängiger Annahme nicht —, er würde aber bestimmte kryptografische Probleme über Shors Algorithmus brechen, weshalb die Post-Quanten-Kryptografie (gitterbasiert, hashbasiert) heute ein bedeutendes Einführungsprogramm ist.