NP-vollständig (englisch NP-complete) beschreibt eine Klasse von Entscheidungsproblemen, die als die härtesten Probleme in NP gelten: Jedes Problem in NP lässt sich in polynomieller Zeit auf ein NP-vollständiges Problem zurückführen (Reduktion) — wer also eines davon schnell löst, löst damit alle Probleme in NP schnell. Für kein NP-vollständiges Problem ist bisher ein polynomieller Algorithmus bekannt, und es gibt starke Hinweise, dass keiner existiert.
Die Klassen P und NP
P umfasst alle Entscheidungsprobleme, die ein Algorithmus in polynomieller Laufzeit lösen kann — praktisch die „schnell lösbaren“ Probleme. NP umfasst Probleme, deren Lösung in polynomieller Zeit verifiziert werden kann, wenn man eine Lösungskandidatin vorgelegt bekommt („non-deterministic polynomial“). Jedes Problem in P liegt auch in NP. Die große offene Frage P = NP? fragt, ob sich die beiden Klassen gleichen — sie ist eines der berühmtesten offenen Probleme der Informatik und eines der Millennium-Probleme des Clay Institute. Ein einziger polynomieller Algorithmus für irgendein NP-vollständiges Problem würde P = NP beweisen.
Definition: in NP und NP-schwer
Ein Problem heißt NP-vollständig, wenn es (a) selbst in NP liegt und (b) NP-schwer ist, sich also jedes Problem aus NP in polynomieller Zeit auf es reduzieren lässt. Der Startpunkt dieser Reduktionskette ist das SAT-Problem: Cook und Levin bewiesen 1971, dass SAT NP-vollständig ist. Von dort aus wird die Eigenschaft per Reduktion weitergereicht — neue Kandidaten werden nachgewiesen, indem man ein bekanntes NP-vollständiges Problem auf sie zurückführt. Zu den bekanntesten NP-vollständigen Problemen gehören 3-SAT, das Hamilton-Pfad- und Hamiltonkreis-Problem, das Rucksackproblem, das Handlungsreisenden-Problem (TSP) und zahlreiche Graphenfärbungsprobleme.
Umgang in der Praxis
Weil exponentielle Worst-Cases drohen, setzt die Praxis auf mehrere Strategien: Backtracking mit intelligentem Beschneiden (Branch-and-Bound), Greedy-Heuristiken, Approximationsalgorithmen mit garantierter Güte sowie die Übersetzung in Spezialformate wie SAT, das moderne SAT-Solver trotz theoretischer Schwere erstaunlich effektiv lösen. Viele reale Instanzen — etwa aus Planung, Logistik oder Verifikation — sind weit kleiner als der Worst Case, und Probleme in Spezialstrukturen wie 2-SAT oder planaren Graphen lassen sich oft doch in polynomieller Zeit lösen.