NP-vollständige Probleme NP-Vollständigkeit

Deterministische polynomielle Algorithmen sind bisher für keines der angegebenen Probleme gefunden worden, und es ist fraglich, ob dies jemals geschehen wird. Diese Probleme sind nämlich NP-vollständig; damit gehören sie zu den schwersten Problemen in NP.

 

NP-vollständige Probleme

Ein NP-schweres Problem ist also mindestens so schwer wie das schwerste Problem in NP. Ein NP-vollständiges Problem ist NP-schwer und liegt selbst in NP; damit gehört es selbst zu den schwersten Problemen in NP.

Wenn es gelingt, auch nur für ein einziges NP-vollständiges Problem p einen deterministischen polynomiellen Algorithmus zu finden, so lassen sich alle Probleme in NP in deterministisch polynomieller Zeit lösen. Denn alle Probleme in NP lassen sich dann ja in deterministisch polynomieller Zeit auf das Problem p reduzieren und sind damit selbst in deterministisch polynomieller Zeit lösbar. Dann wäre also die Menge NP gleich der Menge P. Vieles spricht jedoch dafür, dass dies nicht gilt.

Um zu zeigen, dass ein Problem q, das in NP liegt, NP-vollständig ist, genügt es, ein anderes NP-vollständiges Problem p in polynomieller Zeit auf q zu reduzieren. Denn dass p NP-vollständig ist, bedeutet ja, dass sich alle Probleme in NP in polynomieller Zeit auf p reduzieren lassen. Indem p nun in polynomieller Zeit weiter auf q reduziert wird, lassen sich somit alle Probleme in NP in polynomieller Zeit auf q reduzieren, und somit ist q ebenfalls NP-vollständig (Bild 1).

Als Beispiel für einen solches Vorgehen soll im Folgenden das Erfüllbarkeits­problem (SAT) in polynomieller Zeit auf das Cliquen-Problem reduziert werden [Koz 92]. Wir wissen, dass das Erfüllbarkeits­problem NP-vollständig ist, und wir zeigen dadurch, dass das Cliquen-Problem ebenfalls NP-vollständig ist. Wir transformieren also einen beliebigen gegebenen Fall des Erfüllbarkeits­problems in polynomieller Zeit in einen Fall des Cliquen-Problems, in der Weise, dass die Lösung des Cliquen-Problems (ja oder nein) gleich der Lösung des Erfüllbarkeits­problems ist.

 

Reduktion von SAT auf CLIQUE

Gegeben sei ein Fall des Erfüllbarkeits­problems, also eine boolesche Formel f in konjunktiver Form. Die Formel besteht aus k Oder-Termen c₀, ..., c_k-1, die durch Und verknüpft sind. Die Oder-Terme enthalten Variablen x_i, die auch in negierter Form x_i vorkommen können.

Die Formel wird in folgender Weise in einen ungerichteten Graphen G transformiert. Jedes Vorkommen einer Variablen in der Formel f ist ein Knoten des Graphen. Je zwei Knoten sind durch eine Kante verbunden, außer wenn die entsprechenden Vorkommen der Variablen

• im gleichen Oder-Term liegen  oder
• zueinander negiert sind.

Die Formel f ist genau dann erfüllbar, wenn der Graph G eine k-Clique enthält. Die Formel f wird erfüllt, wenn die Vorkommen der Variablen, die den Knoten der Clique entsprechen, mit dem Wahrheitswert true belegt werden. Diese Belegung ist widerspruchs­frei, denn zueinander negierte Variablen sind nie durch eine Kante verbunden, und in jedem Oder-Term kommt einmal der Wert true vor.

In ähnlicher Weise, durch polynomielle Reduktion eines bekannten NP-vollständigen Problems, sind mittlerweile Tausende von Problemen als NP-vollständig klassifiziert worden [GJ 79]. Das Erfüllbarkeits­problem ist das Ur-Problem, dessen NP-Vollständigkeit auf andere Weise bewiesen worden ist.

Sucht man einen Lösungs­algorithmus für ein Problem, so prüft man zunächst, ob das Problem in NP liegt. Dann besteht eine gewisse Chance, dass es einen effizienten, also deterministisch polynomiellen Algorithmus zur Lösung des Problems gibt. Findet man jedoch keinen solchen, so versucht man, eines der bekannten NP-vollständigen Probleme auf das Problem zu reduzieren, um zu zeigen, dass es NP-vollständig ist und es somit wahrscheinlich keinen effizienten Algorithmus zu seiner Lösung gibt. Dann bleiben nur noch Approximations­verfahren, die eine gewisse Annäherung an die Lösung liefern (die Faktor-2-Annäherung für das metrische TSP ist ein Beispiel) oder probabilistische Verfahren, die mit einer gewissen Wahr­scheinlichkeit die korrekte Lösung liefern (wie etwa der Primzahltest) oder heuristische Verfahren, die mit einer hohen Wahr­scheinlichkeit eine gute Annäherung an die Lösung liefern (z.B. das Verfahren Simulated Annealing).

 

Literatur

[GJ 79]	M.R. Garey, D.S. Johnson: Computers and Intractability. W.H. Freeman (1979)
[Koz 92]	D.C. Kozen: The Design and Analysis of Algorithms. Springer (1992)

 

 

Weiter mit:

 

H.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 25.05.2006   Updated: 05.10.2009