P gegen NP

Ist schnell prüfbar dasselbe wie schnell findbar? Die größte offene Frage der Informatik — und zugleich der Drehpunkt, an dem die Sicherheit jeder heute eingesetzten Verschlüsselung hängt.

Als Nächstes empfohlen → Asymmetrische Kryptographie · CS·KI

Der Beitrag

1971 veröffentlichte Stephen Cook an der University of Toronto The Complexity of Theorem-Proving Procedures und definierte darin 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, Rucksackproblem, allesamt wechselseitig aufeinander reduzierbar. Die Frage, die daraus erwuchs — P gegen NP, also: Lässt sich jedes Problem, dessen Lösung sich schnell prüfen lässt, auch schnell lösen? —, gilt seither als die größte offene Frage der Informatik. Das Clay Mathematics Institute nahm sie 2000 unter seine sieben Millennium-Probleme auf, eine Million Dollar ausgesetzt, bis heute unabgeholt. Die meisten Forscher rechnen mit P ≠ NP. Bewiesen hat es niemand.

In P liegen die Probleme, die sich in polynomieller Zeit lösen lassen — Sortieren, kürzeste Wege, lineare Programmierung sitzen dort bequem. In NP liegen jene, deren vorgeschlagene Lösung sich in polynomieller Zeit prüfen lässt; das Beispiel vom Küchentisch ist Sudoku, wo das Lösen mühsam, das Nachrechnen einer fertigen Lösung aber trivial ist. Die NP-vollständigen Probleme sind die schwersten dieser Klasse: Jedes NP-Problem lässt sich in polynomieller Zeit auf jedes von ihnen zurückführen, ein schnelles Verfahren für eines wäre also ein schnelles Verfahren für alle. Cook zeigte 1971 die NP-Vollständigkeit der booleschen Erfüllbarkeit, Karp dehnte den Beweis im Folgejahr auf Dutzende natürlicher Probleme aus. Gälte P = NP, läge jedes NP-vollständige Problem in P, und die Folgen wären gewaltig: Die Kryptographie bräche zusammen, Optimierung — Logistik, Scheduling, Wirkstoffdesign — würde handhabbar, suchbasierte KI-Systeme sprängen um Größenordnungen nach vorn. Gilt dagegen P ≠ NP, was alles nahelegt, klafft zwischen Prüfen und Finden ein grundsätzlicher Abstand. Drei Linien laufen auf den Glauben an P ≠ NP zu: Jahrzehnte vergeblicher Suche nach polynomiellen Verfahren für SAT oder TSP; formale Resultate, wonach die verfügbaren Beweistechniken — Relativierung, natürliche Beweise, Algebrisierung, nach Razborov-Rudich und Aaronson-Wigderson — die Frage gar nicht entscheiden können; und der schlichte Befund, dass die heutige Kryptographie auf der Härte bestimmter Probleme ruht. Mehrere Ausgänge bleiben möglich. Ein P = NP mit kleinen Konstanten wäre eine praktische Umwälzung; ein galaktischer Algorithmus — Liptons Wort — mit polynomieller Laufzeit, aber astronomischen Konstanten wäre theoretisch reizvoll und praktisch bedeutungslos; und einige, etwa Aaronson, halten ernsthaft für denkbar, dass die Frage von der Standardmathematik unabhängig ist, ganz im Sinne Gödels.

Warum jetztP gegen NP ist der unausgesprochene Angelpunkt der heutigen Technik: Die Verschlüsselung jeder Banküberweisung, jeder HTTPS-Verbindung, jedes sicheren Messengers ruht darauf, dass die für schwer gehaltenen Probleme — Faktorisierung, diskreter Logarithmus, Gitterprobleme — tatsächlich schwer sind. Und die Optimierungsaufgaben von Logistikern, Fluggesellschaften, Chipentwicklern und Pharmafirmen sind in der Praxis durchweg NP-schwer; man behilft sich mit Heuristiken — Simulated Annealing, genetische Algorithmen, Branch-and-Bound, zunehmend gelernte RL-Heuristiken —, die ohne beweisbare polynomielle Garantie gut genug arbeiten. Ein hinreichend großer Quantencomputer würde NP damit nicht generell knacken; dass die Klasse BQP NP enthält, glaubt niemand. Bestimmte kryptographische Probleme würde er über Shors Algorithmus aber sehr wohl brechen — weshalb die Post-Quanten-Kryptographie, gitter- und hashbasiert, inzwischen ein großangelegtes Umstellungsprogramm ist.