P und NP: Wie schwer ist ein Problem?

Kurz: Eine Einteilung von Problemen: P sind solche, die sich schnell lösen lassen; bei NP lässt sich eine vorgeschlagene Lösung schnell prüfen, ob es auch schnell zu finden geht, ist offen.

Genauer: Die Komplexitätstheorie fragt, wie stark der Aufwand mit der Größe der Eingabe wächst. „Schnell“ heißt dabei: höchstens polynomiell, also etwa n², n³ (n ist die Eingabegröße). Ein Aufwand wie 2ⁿ („exponentiell“) wächst so stark, dass schon mittlere Eingaben praktisch unlösbar werden.

Im Detail

P: schnell lösbar

P (polynomielle Zeit) enthält Probleme, die ein Algorithmus in polynomieller Zeit löst: Sortieren, kürzeste Wege in einem Netz, Prüfen, ob eine Zahl in einer Liste steht. Diese Probleme gelten als praktisch beherrschbar.

NP: schnell prüfbar

NP enthält Probleme, bei denen man eine angebotene Lösung in polynomieller Zeit überprüfen kann. Beispiel Sudoku: Ein ausgefülltes Gitter ist schnell kontrolliert, aber eine Lösung zu finden kann (bei großen Varianten) aufwendig sein. Jedes Problem aus P liegt auch in NP.

NP-vollständig und die große Frage

Manche NP-Probleme sind NP-vollständig: Sie gehören zu den schwersten in NP, und ein schneller Algorithmus für eines würde schnelle Algorithmen für alle NP-Probleme liefern. Beispiele: das Problem des Handlungsreisenden (kürzeste Rundreise), Rucksackproblem (Entscheidungsvariante), Erfüllbarkeit logischer Formeln (SAT), Graphfärbung. Ob P = NP gilt, ist eine der bekanntesten ungelösten Fragen der Informatik (eines der sieben Millennium-Probleme). Die meisten Fachleute vermuten, dass P ≠ NP.

Folgen für die Praxis

Für NP-vollständige Probleme verwendet man Näherungsverfahren, Heuristiken (gute, aber nicht beweisbar beste Lösungen), Einschränkungen auf kleine Eingaben oder spezielle Fälle. Auch die Sicherheit moderner Verschlüsselung beruht auf der Annahme, dass bestimmte Probleme schwer sind, wobei diese Probleme (z. B. Faktorisierung) nicht als NP-vollständig bekannt sind.

Siehe auch: Big-O-Notation, Dynamische Programmierung, Greedy-Algorithmen