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 Komplexitätstheorie 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, die diese lösen.

Die Menge aller Sprachen (die Gesamtheit aller Eingaben, die ein Algorithmus akzeptiert), die ein deterministischer Algorithmus (bzw. eine deterministische Turingmaschine) in Polynomailzeit lösen kann, bezeichnet man mit P (siehe polynomieller Algorithmus). NP ist hingegen die Menge aller Sprachen, die ein nicht-deterministischer Algorithmus (bzw. eine nicht-deterministische Turingmaschine) in Polynomialzeit lösen kann (siehe NP-Probleme). Es ist ein zentrales offenes Problem der Informatik, ob P=NP (Menge der P-Probleme ist gleich der Menge der NP-Probleme) oder P $\neq$ NP (Menge der P-Probleme ist eine Teilmenge der NP-Probleme) gilt.

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 Menge der NP-Probleme zu liegen, andererseits aber die Eigenschaft zu besitzen, dass jedes Entscheidungsproblem in dieser Klasse in Polynomialzeit (mit einer deterministischen Turingmaschine) auf dieses reduziert werden kann.

Durch diese 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 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

Erfüllbarkeitsproblem der Aussagenlogik (SAT)
3-SAT
Vertex Cover
das Bin-Packing-Problem
das Rucksackproblem (Knap-Sack-Problem)
...

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 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äß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).

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 Rechenzeit 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 (sogenannte Monte Carlo Algorithmen). 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).