Transformationen

Reduktion von NP-vollständigen Problemen

 aufwärts

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 (rotes Dreieck)
Bild 2: Aus der booleschen Formel f konstruierter Graph G mit 3-Clique (rotes Dreieck)

In ähnlicher Weise, durch polynomielle Reduktion eines bekannten NP-voll­ständigen Problems, sind 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.

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: 05.06.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