NP-vollständige Probleme

NP-Vollständigkeit

 aufwärts

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

Definition:  Ein Problem p heißt NP-schwer, wenn sich jedes Problem r, das in NP liegt, in deterministisch poly­nomieller Zeit auf p reduzieren lässt.

Ein Problem p heißt NP-vollständig, wenn es NP-schwer ist und selbst in NP liegt.

Ein NP-schweres Problem ist also mindestens so schwer wie das schwerste Problem in NP. Ein NP-voll­stä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-voll­ständiges Problem p einen deterministischen poly­nomiellen Algorithmus zu finden, so lassen sich alle Probleme in NP in deterministisch poly­nomieller Zeit lösen. Denn alle Probleme in NP lassen sich dann ja in deterministisch poly­nomieller Zeit auf das Problem p reduzieren und sind damit selbst in deterministisch poly­nomieller 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-voll­ständiges Problem p in poly­nomieller Zeit auf q zu reduzieren. Denn dass p NP-vollständig ist, bedeutet ja, dass sich alle Probleme in NP in poly­nomieller Zeit auf p reduzieren lassen. Indem p nun in poly­nomieller Zeit weiter auf q reduziert wird, lassen sich somit alle Probleme in NP in poly­nomieller Zeit auf q reduzieren, und somit ist q ebenfalls NP-vollständig (Bild 1).

Bild 1: Reduktion eines NP-vollständigen Problems p auf ein Problem q
Bild 1: Reduktion eines NP-vollständigen Problems p auf ein Problem q

Als Beispiel für einen solches Vorgehen soll im Folgenden das Erfüll­barkeits­problem (SAT) in poly­nomieller Zeit auf das Cliquen-Problem reduziert werden [Koz 92]. Wir wissen, dass das Erfüllbarkeitsproblem NP-vollständig ist, und wir zeigen dadurch, dass das Cliquen-Problem ebenfalls NP-vollständig ist. Wir trans­formieren also einen beliebigen gegebenen Fall des Erfüll­barkeits­problems in poly­nomieller 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üll­barkeits­problems ist.

Reduktion von SAT auf CLIQUE

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

Die Formel wird in folgender Weise in einen ungerichteten Graphen G trans­formiert. 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 ent­sprechenden Vorkommen der Variablen

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 Wahrheits­wert 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.

Beispiel:  Die Formel sei

f  =  (x0  oder  x1)  und  (x0  oder  x1)  und  (x0  oder  x1)

Sie besteht aus den drei Oder-Termen c0, c1, c2, d.h. es ist k = 3. Der entsprechend konstruierte Graph ist in Bild 2 dargestellt. Er enthält die 3-Clique mit den Knoten x0 in c0, x1 in c1 und x1 in c2. Mit x0 = true und x1 = false ist die Formel somit erfüllt.

Bild 2: Aus der booleschen Formel f konstruierter Graph G mit 3-Clique
Bild 2: Aus der booleschen Formel f konstruierter Graph G mit 3-Clique

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

Lösungsansätze

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 poly­nomiellen Algorithmus zur Lösung des Problems gibt. Findet man jedoch keinen solchen, so versucht man, eines der bekannten NP-voll­ständigen Probleme auf das Problem zu reduzieren, um zu zeigen, dass es NP-vollständig ist und es somit wahr­scheinlich 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­schein­lich­keit die korrekte Lösung liefern (wie etwa der Primzahltest) oder heuristische Verfahren, die mit einer hohen Wahr­schein­lich­keit eine gute Annäherung an die Lösung liefern (z.B. das Verfahren Simulated Annealing).

Aufgaben

Aufgabe 1:  Das Problem des Hamilton­schen Kreises (HC) ist NP-vollständig. Reduzieren Sie HC polynomiell auf das Travelling Salesman Problem (TSP) und zeigen Sie so, dass TSP ebenfalls NP-vollständig ist.

Hinweis: Benutzen Sie die Formulierung von TSP als Ent­scheidungsproblem. Geben Sie eine Trans­formation an, die einen beliebigen Fall von HC in einen Fall von TSP umwandelt, derart dass deren Lösungen (ja oder nein) gleich sind. Welche Zeit­komplexität hat die Trans­formation?

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:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 25.05.2006   Updated: 21.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik