NP-Vollständigkeit

Begriff und Bedeutung

Ein Problem heißt NP-vollständig, wenn es zu den schwierigsten Problemen der Komplexitätsklasse NP gehört. Es muss zugleich in NP liegen und NP-schwer sein. Umgangssprachlich bedeutet dies, dass eine effiziente Lösung vermutlich nicht möglich ist. NP-Vollständigkeit ist ein zentraler Begriff der Komplexitätstheorie, eines Teilgebiets der theoretischen Informatik.

Formal wird NP-Vollständigkeit nur für Entscheidungsprobleme definiert. Bei diesen lautet die Antwort ausschließlich „Ja“ oder „Nein“. Ein Entscheidungsproblem L ist genau dann NP-vollständig, wenn gilt:

• L ∈ NP;
• ∀ L′ ∈ NP: L′ ≼ₚ L.

Die zweite Bedingung bedeutet, dass jedes Problem in NP durch eine Polynomialzeitreduktion auf L zurückgeführt werden kann. Eine solche Reduktion muss auf einem deterministischen Rechner höchstens polynomielle Zeit benötigen. Die Klasse aller NP-vollständigen Probleme wird mit NP-C (complete) bezeichnet.

Für viele NP-vollständige Probleme gibt es dennoch Verfahren, die typische Eingaben in akzeptabler Zeit lösen. Für kein NP-vollständiges Problem ist bisher nachgewiesen, dass es in polynomieller Zeit lösbar ist. Falls ein einziges NP-vollständiges Problem in polynomieller Zeit lösbar wäre, wäre jedes Problem in NP in polynomieller Zeit lösbar. Dieser Zusammenhang ist ein zentraler Teil des P-NP-Problems; seine praktischen Folgen könnten groß sein, müssen es aber nicht notwendigerweise sein.

Nachweis der NP-Vollständigkeit

Der Nachweis, dass ein Problem in NP liegt, ist meistens einfach. Man „rät“ eine mögliche Lösung und zeigt anschließend, dass ein deterministisch arbeitender Rechner in Polynomialzeit überprüfen kann, ob diese Lösung tatsächlich korrekt ist. Das Raten der richtigen Lösung bildet den Nichtdeterminismus ab.

Der Nachweis der NP-Schwere ist schwieriger. Statt direkt zu zeigen, dass jedes beliebige Problem aus NP auf das betrachtete Problem reduziert werden kann, nimmt man gewöhnlich ein ähnliches Problem, dessen NP-Vollständigkeit bereits bekannt ist. Man reduziert dieses bekannte Problem in Polynomialzeit auf das neue Problem. Wegen der Transitivität von Polynomialzeitreduktionen folgt daraus, dass auch alle anderen Probleme aus NP auf das neue Problem reduzierbar sind.

Die Definition setzt streng genommen voraus, dass NP-vollständige Probleme überhaupt existieren. Ein solches Problem lässt sich zwar leicht konstruieren, doch künstliche Konstruktionen sind kaum praxisrelevant. Stephen A. Cook zeigte daher direkt, dass das Erfüllbarkeitsproblem der Aussagenlogik NP-vollständig ist. Für dieses erste wichtige Beispiel konnte der Nachweis noch nicht über die Transitivität bereits bekannter Polynomialzeitreduktionen geführt werden.

Entstehung des Konzepts

Stephen A. Cook führte den Begriff der NP-Vollständigkeit 1971 in seinem heute so genannten Satz von Cook ein. Er bewies darin, dass das Erfüllbarkeitsproblem der Aussagenlogik NP-vollständig ist.

Richard Karp legte 1972 eine weitere wichtige Arbeit vor. Er nutzte die Technik der Polynomialzeitreduktion konsequent und wies die NP-Vollständigkeit für 21 weitere populäre Probleme nach. Dadurch wurde die Theorie der NP-Vollständigkeit deutlich bekannter. Seit Cook wurde das Konzept außerdem auf beliebige Komplexitätsklassen ausgeweitet.

NP-Äquivalenz und Approximation

Bei Suchproblemen und Optimierungsproblemen spricht man streng genommen nicht von NP-Vollständigkeit, sondern von NP-Äquivalenz. NP-Vollständigkeit bezieht sich nur auf Entscheidungsprobleme, die sich auf das Wortproblem einer formalen Sprache zurückführen lassen und daher nur die Antworten „Ja“ oder „Nein“ besitzen. Im allgemeinen Sprachgebrauch wird diese Unterscheidung jedoch oft nicht eingehalten, weil verschiedene Problemtypen ineinander überführbar beziehungsweise aufeinander reduzierbar sind.

Probleme in NP können außerdem danach unterschieden werden, wie gut sie sich näherungsweise lösen lassen. Das Graphen-Färbungsproblem ist beispielsweise nur sehr schlecht approximierbar. Andere Probleme lassen sich mithilfe sogenannter Approximationsschemata beliebig gut approximieren.

Starke und schwache NP-Vollständigkeit

Ein NP-vollständiges Problem heißt stark NP-vollständig, wenn es auch dann NP-vollständig bleibt, wenn die Eingabe nur Zahlen als numerische Parameter enthält, deren Größe im Verhältnis zur Eingabelänge polynomiell beschränkt ist. Gleichbedeutend kann man die numerischen Parameter im Unärsystem in die Eingabe schreiben; bleibt das Problem dann NP-vollständig, ist es stark NP-vollständig. Solche Probleme besitzen unter der Annahme NP ≠ P keine pseudopolynomiellen Algorithmen.

Ein pseudopolynomieller Algorithmus hat eine Laufzeit, die polynomiell ist, wenn die Größe aller in der Eingabe vorkommenden Zahlen polynomiell durch die Eingabelänge beschränkt ist. Beim Rucksackproblem existiert ein solcher Algorithmus. Dynamische Programmierung erreicht beispielsweise eine Laufzeit von O(n² · V), wobei n die Eingabelänge und V die Schranke für den maximal erlaubten Nutzwert bezeichnet. Die Laufzeit ist daher polynomiell, wenn V im Verhältnis zur Eingabelänge nur polynomiell groß ist. NP-vollständige Probleme, für die ein pseudopolynomieller Algorithmus existiert, heißen schwach NP-vollständig.