NP-Vollständigkeit

Der Begriff NP-Vollständigkeit ist ein Begriff aus der Komplexitätstheorie der theoretischen Informatik, der im Jahre 1972 von Stephen Cook durch den Satz von Cook eingeführt wurde. Er klassifiziert eine Menge von Entscheidungsproblemen, die in gewisser Hinsicht besonders schwierig sind und für die angenommen wird, dass keine effizienten Algorithmen existieren, die diese lösen.

Siehe auch: P/NP-Problem

Definition

Ein Problem (genauer: ein Entscheidungsproblem) L heißt NP-vollständig genau dann, wenn

• L in der Klasse NP liegt, das heißt ${\mathit {L}}\in {\mathit {NP}}$ und
• es für jedes Problem in NP eine Polynomialzeitreduktion auf L gibt.

Nachweis der NP-Vollständigkeit

Der Nachweis der ersten Eigenschaft für ein Problem ist in aller Regel leicht. Man "rät" eine Lösung und zeigt, das man in Polynomialzeit verifizieren kann, ob die Lösung wirklich zutrifft.

Der Nachweis der zweiten Eigenschaft, die man für sich allein auch als NP-Schwere (oder oft - eigentlich falsch - aus dem englischen zurückübersetzt als NP-Härte) bezeichnet ist schwieriger. Insbesondere bereitet es Probleme, eine Aussage für beliebige Probleme in NP zu zeigen. Daher nimmt man gewöhnlich ein ähnliches Problem, für das die NP-Vollständigkeit schon bekannt ist und reduziert es auf dasjenige Problem, für das man die Eigenschaft der NP-Schwere zeigen will. Aus der Transitivität von Polynomialzeitreduktionen folgt dann, dass alle Probleme aus NP auch auf das betrachtete Problem reduzierbar sind.

Die obige Definition erfordert streng genommen einen Existenzbeweis. Es ist nicht sofort ersichtlich, dass derartige Probleme überhaupt existieren. Es lässt sich aber leicht ein solches Problem konstruieren. Allerdings ist ein derart konstruiertes Problem kaum praxisrelevant. Cook konnte jedoch zeigen, dass das Erfüllbarkeitsproblem der Aussagenlogik NP-vollständig ist und hat damit für ein praxisrelevantes Problem den Nachweis geführt. Dieser Beweis konnte im Gegensatz zu anderen Problemen natürlich noch nicht wie oben dargestellt über die Transitivität von Polynomialzeitreduktionen geführt werden und musste direkt erfolgen.

Klassische Vertreter NP-vollständiger Probleme

• Erfüllbarkeitsproblem der Aussagenlogik (SAT)
• 3-SAT
• Max2SAT
• Vertex Cover
• Clique
• Partition
• gerichtetes bzw. ungerichtetes Hamiltonkreisproblem
• gerichtetes bzw. ungerichtetes Hamiltonpfadproblem
• Problem des Handlungsreisenden (traveling salesman problem)
• das Bin-Packing-Problem
• das Rucksackproblem (Knap-Sack-Problem)
• 3COLOR
• Exact Cover
• Subset Sum

NP-Äquivalenz

Der Begriff NP-Vollständigkeit ist nur für Entscheidungsprobleme definiert, also solche Probleme, die sich auf das Wortproblem einer formalen Sprache zurückführen lassen, für die als Antwort also nur entweder Ja oder Nein in Frage kommt. Für Optimierungsprobleme und Suchprobleme gibt es den Begriff der NP-Äquivalenz.

Approximation

Probleme die in NP liegen, lassen sich weiter in ihrer Komplexität unterteilen, je nach dem, wie gut sie sich approximativ lösen lassen. Das Graphen-Färbungsproblem lässt sich beispielsweise nur sehr schlecht approximativ lösen, während andere Probleme beliebig gut mittels so genannten Approximationsschemata approximieren lassen.

Starke und schwache NP-Vollständigkeit

Weiter kann man die NP-vollständigen Probleme noch einteilen in

• stark NP-vollständige und
• schwach NP-vollständige Probleme

Ein NP-vollständiges Problem heißt stark NP-vollständig, falls es auch dann noch NP-vollständig ist, wenn die Eingabe nur aus Zahlen besteht, deren Größe polynomiell in der Eingabelänge beschränkt ist. Andernfalls heißt das Problem schwach NP-vollständig. Für stark NP-vollständige Probleme kann es - unter der Annahme NP ungleich P - noch nicht einmal so genannte pseudopolynomielle Algorithmen geben. Das sind Algorithmen, deren Laufzeit polynomiell ist, wenn die Größe aller in der Eingabe vorkommenden Zahlen polynomiell in der Eingabelänge beschränkt sind.

Siehe auch: NP (Komplexitätsklasse), Komplexitätsklasse