Unterabschnitte
3SAT ist das Erfüllbarkeitsproblem mit der Voraussetzung, daß in der Formel
höchstens 3 Literale pro Klausel sein dürfen.
Es ist klar, daß man für den NP-Vollständigkeitsbeweis genauso wie bei SAT die Guess-And-Check-Methode bei 3SAT anwenden kann.
Wir können SAT auf 3SAT polynomiell reduzieren:
1.Schritt
Mit Hilfe der De-Morgan-Regeln
und der Regel der doppelten Verneinung
erstellen wir einen Syntaxbaum aus der Eingabeformel
, in dem die Negationen nur in den Blättern vorhanden sind. Der so entstandene Syntaxbaum ist offensichtlich äquivalent zu der Eingabeformel
.
2.Schritt
Wir formen den so entstandenen Syntaxbaum um.
Dafür geben wir einem jeden Verknüpfungsknoten einen Namen, wobei
der Wurzelverknüpfungsknoten ist.
Nun kommt ein Äquivalenzoperator
ins Spiel. Wir definieren denselben folgendermaßen
35:
bedeutet:
ist 1, wenn
ist 0, wenn
Wir können auch folgendes Konstrukt erstellen:
Dies bedeutet, daß wenn der rechte und der linke Teil äquivalent sind, die Formel 1 ist, wenn beide Teile nicht äquivalent sind, dann ist der Wert der Formel 0. Wir können uns dies an einem Beispiel
36 klar machen:
|
|
|
|
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
Aufgrund dieser Wahrheitstabellen können wir nun die Formeln
konstruieren:
Wir können für jeden Verknüpfungsknoten
des Syntaxbaumes eine solche Formel
erstellen. Diese fügen wir zusammen:
In den obigen Formel bemerken wir, daß wir höchstens immer 3 Literale pro Klausel in der Formel stehen haben
37. Die Formeln
sind also 3KNF Formeln. Somit ist auch
eine 3KNF Formel. Wir können uns klar machen, daß
.
3SAT
CP:
Wir erzeugen den Graphen für das CP folgendermaßen:
- Für jede Klausel mit jeweils 3 Literalen erzeugen wir auch 3 Knoten.
- Wir zeichnen jeweils eine Kante zwischen allen Literalen zweier Klauseln. Einzige Ausnahme ist hierbei, daß die beiden Literale komplementär zueinander sind.
- Wir zeichnen niemals eine Kante zwischen den Literalen ein und derselben Klausel.
Wenn es eine Clique der Größe
gibt, wobei
die Anzahl der Klauseln in 3SAT ist, so ist die Formel erfüllbar.
Beispiel
|
|
|
|
|
|
1.Klausel |
|
|
|
|
|
|
2.Klausel |
|
|
|
|
|
|
3.Klausel |
Da es eine Dreier-Clique gibt, ist die aussagelogische Formel für eine Belegung wahr.
Gliedert sich in 2 Teile:
- SUBSUM RP (Spezialisierung)
- 3SAT SUBSUM (Transformation)
Teil 1:
Für die NP-Vollständigkeit von
genügt es nachzuweisen, daß
, da
ein Spezialfall von
ist. Um
auf
zu reduzieren
38 setzen wir das Gewicht für jedes Element gleich 1.
Die Frage von
ist es nun:
Gibt es eine Teilmenge aller Elemente mit dem Gewinn
?
Teil 2:
Es gilt zu beweisen
39:
Sei die
-Formel von der folgenden Form:
Die i-te Klausel hat folgende Form:
Wir setzen den zu erzielenden Gewinn gleich
40
Wir erstellen für jedes Literal
vier Gewinne für
41:
Dabei stellt
das Vorkommen von
in der k-ten Klausel da.
Dasselbe für
:
und
garantieren, daß kein Literal
und
gleichzeitig ist.
Nun erstellen wir noch die beiden Gewinne
und
für jedes Literal
zum Auffüllen, welche an j-ter Stelle eine
bzw. eine
stehen haben:
Aus den so entstandenen Gewinnen läßt sich nun genau der Rucksack voll ausschöpfen (
), wenn die
-Formel erfüllt ist.
Beispiel
Gegeben sei folgende aussagelogische Formel:
|
|
|
|
|
|
1.Klausel |
|
|
|
|
|
|
2.Klausel |
|
|
|
|
|
|
3.Klausel |
|
|
|
|
|
|
4.Klausel |
Der SUBSUM-Gewinn für 4 Klauseln und 3 verschiedene Literale ist
Wir erzeugen folgende Gewinne
Klauselnr. |
1234 |
|
Im Rucksack |
|
1100 |
001 |
|
|
0011 |
001 |
|
|
1001 |
010 |
|
|
0110 |
010 |
|
|
0101 |
100 |
|
|
1010 |
100 |
|
|
1000 |
000 |
|
|
2000 |
000 |
|
|
0100 |
000 |
|
|
0200 |
000 |
|
|
0010 |
000 |
|
|
0020 |
000 |
|
|
0001 |
000 |
|
|
0002 |
000 |
|
Eine gültige Belegung mit der wir genau den richtigen Gewinn treffen ist also
Bei 0/1 Linear Programming ist ein lineares Gleichungssystem
mit ganzzahligen Koeffizienten gegeben. Gefragt ist, ob es einen Lösungsvektor
gibt, dessen Komponenten
oder
sind
42, so daß die Gleichung
wahr ist.
- 0/1 ILP ist in NP
Mittel Guess-and-Check-Verfahren läßt sich der Vektor ermitteln und anschließend überprüfen.
-
Wir reduzieren in polynomieller Zeit auf , d.h wir erzeugen für einen Algorithmus mit Hilfe von .
Sei die Formel
von
wieder der Form
Die Matrix
ist nun
Zellen breit und
Zellen hoch, wobei
die Anzahl der unterschiedlichen Literale und
die Anzahl der Klauseln in
ist. Wir verwenden für das O/1-ILP in den einzelnen Zeilen der Matrix für ,,true'' eine
für ,,false'' eine
.
- Die ersten Ungleichungen stellen sicher, daß ein und dasselbe Literal nicht gleichzeitig wahr und falsch sein kann, bzw. auch eines der beiden sein muß und nicht gar nichts sein kann43:
()te Formel:
()te Formel:
- Die letzten Ungleichungen sagen, daß pro Klausel ein Literal wahr sein muß:
Es ist leicht einsichtig, warum dieses
-Problem genau dann auch erfüllt ist, wenn die
von
auch erfüllt ist.
Weitere NPC-Beweise findet man in der Fachliteratur.
Fußnoten
- ... folgendermaßen35
- op ist ein Operator also entweder oder
- ... Beispiel36
- Dies steht auf Seite 944 im Cormen: Introduction to Algorithms
- ... haben37
- Wenn wir weniger als drei haben, können wir ein weiteres Literal ergänzen, indem wir ein Literal der Klausel verdoppeln.
- ... reduzieren38
-
- ... beweisen39
- Wir erstellen einen Algorithmus für mit Hilfe von .
- ... gleich40
- Der zu erzielenden Gewinn für 3 Klauseln und 3 Literale wäre also 444111 (In Worten: vierhundertvierundvierzigtausendeinhundertundelf)
- ...41
- Also, wenn wir 3 unterschiedliche Literale haben (
), dann haben wir Gewinne
- ... sind42
- D.h. Maskierung der Zeilen in der Matrix mit dem Vektor x. Nur dort wo eine 1 vorkommt, wird auch die Spalte genommen.
- ... kann43
- und
können, wie man an den Formeln sieht nicht gleichzeitig oder sein, sondern müssen paarweise verschieden sein.