Transformationen
Reduktion von NP-vollständigen Problemen
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).
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üllbarkeitsproblem (SAT) in polynomieller 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 transformieren also einen beliebigen gegebenen Fall des Erfüllbarkeitsproblems 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üllbarkeitsproblems ist.
Reduktion von SAT auf CLIQUE
Gegeben sei ein Fall des Erfüllbarkeitsproblems, 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 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 widerspruchsfrei, 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 ∨ x1) ∧ (x0 ∨ x1) ∧ (x0 ∨ 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)
In ähnlicher Weise, durch polynomielle Reduktion eines bekannten NP-vollständigen Problems, sind Tausende von Problemen als NP-vollständig klassifiziert worden [GJ 79]. Das Erfüllbarkeitsproblem ist das Ur-Problem, dessen NP-Vollständigkeit auf andere Weise bewiesen worden ist.
Aufgaben
Aufgabe 1: Das Problem des Hamiltonschen 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 Entscheidungsproblem. Geben Sie eine Transformation an, die einen beliebigen Fall von HC in einen Fall von TSP umwandelt, derart dass deren Lösungen (ja oder nein) gleich sind. Welche Zeitkomplexität hat die Transformation?
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]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 25.05.2006 Updated: 08.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden