NP-Vollständigkeit

Achtung: Dieser Artikel setzt Fachwissen voraus, welches hier nicht in Kürze dargelegt werden kann. Der Leser sollte zum Verständnis wenigstens mit den Begriffen Turingmaschine, Entscheidungsproblem, Algorithmus, Polynomialzeit-Algorithmus, Polynomialzeit-Reduktion und formale Sprache ausreichend vertraut sein.'

Der Begriff NP-Vollständigkeit ist ein Begriff aus der theoretischen Informatik. Er klassifiziert eine Menge von Entscheidungsproblemen, die in gewisser Hinsicht besonders schwierig sind und für die angenommen wird, dass keine effizienten Algorithmen existieren.

Da der Nicht-Existenzbeweis eines polynomiellen Algorithmus sehr schwierig ist (es gibt bis heute so gut wie keine Methoden derartiges nachzuweisen), beschränkt man sich darauf Probleme zueinander in Beziehung zu setzen und so abzuleiten, wie schwer diese sind. NP-vollständige Probleme zeichnen sich nun dadurch aus selbst in der Klasse der NP-Probleme zu liegen (also zu der Klasse von Problemen zu gehören, für die eine nichtdeterministische Turingmaschine existiert, die das Problem in Polynomialzeit löst), andererseits aber jedes Entscheidungsproblem in dieser Klasse in Polynomialzeit (mit einer deterministischen Turingmaschine) auf dieses reduziert werden kann.

Durch die spezielle Definition kann man nun annehmen, dass die NP-vollständigen Probleme in gewisser Hinsicht die schwierigsten Probleme in der Klasse der NP-Probleme überhaupt sind. Allerdings bedarf es zur Rechtfertigung des Begriffs eines Existenzbeweises solcher Probleme, der erstmals von E. Karp im Jahre 1972 geliefert wurde.

P/NP

Aus der Definition der NP-Vollständigkeit folgt nun, dass entweder alle Probleme in NP auch in P liegen, d.h. in der Klasse aller Probleme liegen, die sich in Polynomialzeit mit einer deterministischen Turingmaschine lösen lassen (die Umkehrung ist trivial, alle Probleme aus P liegen auch in NP), oder aber zumindest für die NP-vollständigen Probleme kein deterministischer Polynomialzeit-Algorithmus existiert. Welcher der beiden Fälle zutrifft ist bis heute nicht bekannt. Diese häufig mit "P=NP?" abgekürzt Fragestellung gilt derzeit als die wichtigste Fragestellung der Informatik überhaupt und wird auch in der Mathematik als eine der sieben schwierigsten und wichtigsten Fragestellungen betrachtet.

Definition

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

$L\in \mathbb {NP}$
Es gibt eine Polynomialzeitreduktion aller Probleme in NP auf L

Genau so wird dies natürlich nicht so häufig für konkrete Probleme gezeigt, weil es recht schwierig ist, eine Aussage für beliebige Probleme in NP zu zeigen. Vielmehr nimmt man ein 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-Vollständigkeit zeigen will. Aus der Transitivität von Polynomialzeitreduktionen folgt dann, dass alle Probleme aus NP auch auf das betrachtete Problem reduzierbar sind.

Klassische Vertreter NP-vollständiger Probleme sind etwa

SAT
3-SAT
Vertex Cover
das Bin Packing Problem
das Rucksackproblem (auch bekannt als Knap Sack Problem)
...

NP-Aquivalenz

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 Optimierungsprobleme und Suchprobleme gibt es den Begriff der NP-Äquivalenz.

Approximation

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

NP-Schwere (NP-Härte)

Ein verwandter Begriff zur NP-Vollständigkeit ist die NP-Schwere (oft auch als "NP-Härte" bezeichnet - aus dem englischen zurückübersetzt). Der Begriff NP-Vollständigkeit bezieht sich nur auf Probleme aus NP (also Entscheidungsprobleme). Ein Problem heißt dann NP-schwer, wenn die Bedingungen von oben erfüllt sind, das Problem jedoch nicht in NP liegt.

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

Bleibt das Problem auch noch mit unärer Kodierung der Eingabe NP-vollständig, so heißt das Problem stark NP-vollständig, ansonsten schwach NP-vollständig. Eine alternative Definition besagt, dass es für schwach NP-vollständige Probleme so genannte pseudopolynomielle Algorithmen gibt, für stark NP-vollständige Probleme dagegen nicht. Algorithmen, bei denen in der Laufzeitschranke eine Zahl vorkommt, die nicht polynomiell von der Eingabelänge abhängt, nennt man pseudopolynomiell, da die Laufzeit nicht zwangsläufig polynomiell sein muss - etwa, wenn diese Zahl so groß wird, dass sie exponentiell in der Eingabelänge ist.

Lösungsansätze

Probleme dieser Problemklasse haben die unangenehme Eigenschaft, dass die Rechentzeit bei zunehmender Datenmenge rasch ins astronomische steigt. Eine vollständige und optimale Lösung ist daher bestenfalls für kleine Datenmengen zu erreichen. Im Rahmen der Software-Entwicklung folgt man drei Lösungsansätzen, um ein solches Problem anzuprogrammieren:

Man schreibt tatsächlich einen optimalen Algorithmus, geht jedoch davon aus, dass die zu verarbeitende Datenmenge stets in einem Bereich bleibt, der klein genug ist, um die Lösung abzuwarten.
Man wählt einen heuristischen Algortithmus, also ein regelbasiertes System, und sucht nicht nach einer optimalen Lösung, sondern nur nach einer Lösung, die für die konkrete Aufgabe gut genug ist.
Man verzichtet darauf, dass der Algorithmus korrekt ist, und wählt eine Methode, die nur mit hoher Wahrscheinlichkeit eine korrekte (optimale) Lösung liefert. Unter hoher Wahrscheinlichkeit versteht man, dass die Wahrscheinlichkeit, dass der Prozessor auf Grund eines Hardware-Fehlers ein falsches Ergebnis liefert, statistisch höher ist, als eine statistische Fehlleistung des Algorithmus (typische akzeptierte Werte liegen bei Fehlerwahrscheinlichkeiten ab 1:1.000.000.000 bis 1:1.000.000.000.000, also um wenigstens eine Zehnerpotenz unwahrscheinlicher als eine 6 mit Superzahl im Lotto).