Einige NP-Vollständigkeitsbeweise ::: Theoretische Informatik

3SAT ist das Erfüllbarkeitsproblem mit der Voraussetzung, daß in der Formel $\alpha$ 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:

$\begin{displaymath}SAT\leq_{poly}3SAT\end{displaymath}$

1.Schritt
Mit Hilfe der De-Morgan-Regeln

$\begin{displaymath}\neg(a\wedge b)\equiv (\neg a)\vee(\neg b)\end{displaymath}$

$\begin{displaymath}\neg(a\vee b)\equiv (\neg a) \wedge (\neg b)\end{displaymath}$

und der Regel der doppelten Verneinung

$\begin{displaymath}a=\neg\neg a\end{displaymath}$

erstellen wir einen Syntaxbaum aus der Eingabeformel $\alpha$ , in dem die Negationen nur in den Blättern vorhanden sind. Der so entstandene Syntaxbaum ist offensichtlich äquivalent zu der Eingabeformel $\alpha$ .
2.Schritt
Wir formen den so entstandenen Syntaxbaum um.

Dafür geben wir einem jeden Verknüpfungsknoten einen Namen, wobei $v_{0}$ der Wurzelverknüpfungsknoten ist.

Nun kommt ein Äquivalenzoperator $\leftrightarrow$ ins Spiel. Wir definieren denselben folgendermaßen³⁵:
$v\leftrightarrow v_{L}\,op\,\,v_{R}$ bedeutet:

ist 1, wenn $v_{L}\,op\,\,v_{R} \equiv 1$

ist 0, wenn $v_{L}\,op\,\,v_{R} \equiv 0$
Wir können auch folgendes Konstrukt erstellen:

$\begin{displaymath}(v\leftrightarrow v_{L}\,op\,\,v_{R})\end{displaymath}$

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³⁶ klar machen:

	$v_{L}$	$v_{R}$	$(v\leftrightarrow v_{L}\wedge v_{R})$
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 $\alpha_{v}'$ konstruieren:

$(v\leftrightarrow v_{L}\vee v_{R}) \equiv (v\vee \neg v_{L})\wedge (\neg v \vee v_{L} \vee v_{R})\wedge (v \vee \neg v_{R})$
$(v\leftrightarrow v_{L}\wedge v_{R}) \equiv (\neg v \vee v_{L})\wedge (\neg v \vee v_{R})\wedge (v\vee \neg v_{L}\vee \neg v_{R})$

Wir können für jeden Verknüpfungsknoten

des Syntaxbaumes eine solche Formel $\alpha_{v}'$ erstellen. Diese fügen wir zusammen:

$\begin{displaymath}\alpha'=\left(\bigwedge_{v}\alpha_{v}'\right)\wedge v_{0}\end{displaymath}$

In den obigen Formel bemerken wir, daß wir höchstens immer 3 Literale pro Klausel in der Formel stehen haben³⁷. Die Formeln $\alpha_{v}'$ sind also 3KNF Formeln. Somit ist auch $\alpha'$ eine 3KNF Formel. Wir können uns klar machen, daß $\alpha'\equiv\alpha$ .

3SAT $\leq_{poly}$ CP (Transformation)

3SAT $\rightarrow$ 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

	$x_{1}$	$\vee$	$x_{2}$	$\vee$	$x_{3}$	1.Klausel
$\wedge$	$\overline{x_{1}}$	$\vee$	$x_{2}$	$\vee$	$\overline{x_{3}}$	2.Klausel
$\wedge$	$\overline{x_{1}}$	$\vee$	$x_{2}$	$\vee$	$x_{3}$	3.Klausel

Da es eine Dreier-Clique gibt, ist die aussagelogische Formel für eine Belegung wahr.

3SAT $\leq_{poly}$ RP (Transformation sowie auch Spezialisierung)

Gliedert sich in 2 Teile:

SUBSUM $\leq_{poly}$ RP (Spezialisierung)
3SAT $\leq_{poly}$ SUBSUM (Transformation)

Teil 1:
Für die NP-Vollständigkeit von

genügt es nachzuweisen, daß $SUBSUM \in NPC$ , da

ein Spezialfall von

ist. Um

auf

zu reduzieren³⁸ 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³⁹:

$\begin{displaymath}3SAT\leq_{poly}SUBSUM\end{displaymath}$

Sei die

-Formel von der folgenden Form:

$\begin{displaymath}\alpha=\bigwedge_{1\leq i\leq k}\left(A_{i,1}\vee A_{i,2}\vee A_{i,3}\right)\end{displaymath}$

Die i-te Klausel hat folgende Form:

$\begin{displaymath}\gamma_{i}=A_{i,1}\vee A_{i,2}\vee A_{i,3}\end{displaymath}$

Wir setzen den zu erzielenden Gewinn gleich⁴⁰

$\begin{displaymath}\begin {array}{crl}q=&\underbrace{44\ldots 44}&\underbrace{11... ...&der&verschiedenen\,Literale\,x_{j}\\ &Klauseln&\\ \end{array}\end{displaymath}$

Wir erstellen für jedes Literal $x_{j}$ vier Gewinne für

⁴¹:

$\begin{displaymath}\begin {array}{cccl}v_{j}=b_{j,1}b_{j,2}\ldots b_{j,i}\ldots ... ...underbrace{\ldots 00}\\ &j-1&&k-j-1\\ &mal&&mal\\ \end{array}\end{displaymath}$

Dabei stellt $b_{j,k}$ das Vorkommen von $x_{j}$ in der k-ten Klausel da. $b_{j,k}\in\{0,1,2,3\}$

Dasselbe für $\overline{x_{j}}$ :

$\begin{displaymath}\begin {array}{cccl}\overline{v_{j}}=\overline{b_{j,1}}\,\ove... ...underbrace{\ldots 00}\\ &j-1&&k-j-1\\ &mal&&mal\\ \end{array}\end{displaymath}$

$v_{j}$ und $\overline{v_{j}}$ garantieren, daß kein Literal

und

gleichzeitig ist.
Nun erstellen wir noch die beiden Gewinne $c_{i}$ und $d_{i}$ für jedes Literal $x_{j}$ zum Auffüllen, welche an j-ter Stelle eine

bzw. eine

stehen haben:

$\begin{displaymath}c_{i}=00\ldots 010\ldots 0\,\,\,00\ldots 0 \ldots 0\end{displaymath}$

$\begin{displaymath}d_{i}=00\ldots 020\ldots 0\,\,\,00\ldots 0 \ldots 0\end{displaymath}$

Aus den so entstandenen Gewinnen läßt sich nun genau der Rucksack voll ausschöpfen ( $\sum p_{i}=q$ ), wenn die

-Formel erfüllt ist.

Beispiel
Gegeben sei folgende aussagelogische Formel:

	$x_{1}$	$\vee$	$x_{2}$	$\vee$	$\overline{x_{3}}$	1.Klausel
$\wedge$	$x_{1}$	$\vee$	$\overline{x_{2}}$	$\vee$	$x_{3}$	2.Klausel
$\wedge$	$x_{1}$	$\vee$	$\overline{x_{2}}$	$\vee$	$\overline{x_{3}}$	3.Klausel
$\wedge$	$\overline{x_{1}}$	$\vee$	$x_{2}$	$\vee$	$x_{3}$	4.Klausel

Der SUBSUM-Gewinn für 4 Klauseln und 3 verschiedene Literale ist

$\begin{displaymath}4444111\end{displaymath}$

Wir erzeugen folgende Gewinne

Klauselnr.	1234		Im Rucksack
$v_{1}=$	1100	001	$\bullet$
$\overline{v_{1}}=$	0011	001
$v_{2}=$	1001	010	$\bullet$
$\overline{v_{2}}=$	0110	010
$v_{3}=$	0101	100
$\overline{v_{3}}=$	1010	100	$\bullet$
$c_{1}=$	1000	000	$\bullet$
$d_{1}=$	2000	000
$c_{2}=$	0100	000	$\bullet$
$d_{2}=$	0200	000	$\bullet$
$c_{3}=$	0010	000	$\bullet$
$d_{3}=$	0020	000	$\bullet$
$c_{4}=$	0001	000	$\bullet$
$d_{4}=$	0002	000	$\bullet$

Eine gültige Belegung mit der wir genau den richtigen Gewinn treffen ist also

$\begin{displaymath}v_{1}+v_{2}+\overline{v_{3}}+c_{1}+c_{2}+d_{2}+c_{3}+d_{3}+c_{4}+d_{4}\end{displaymath}$

0/1 Integer Linear Programming (Transformation)

Bei 0/1 Linear Programming ist ein lineares Gleichungssystem $A\cdot x\geq b$ mit ganzzahligen Koeffizienten gegeben. Gefragt ist, ob es einen Lösungsvektor

gibt, dessen Komponenten

oder

sind⁴², so daß die Gleichung $A\cdot x\geq b$ wahr ist.

0/1 ILP ist in NP
Mittel Guess-and-Check-Verfahren läßt sich der Vektor ermitteln und anschließend überprüfen.
$3SAT \leq_{poly} 0/1-ILP$
Wir reduzieren in polynomieller Zeit auf , d.h wir erzeugen für einen Algorithmus mit Hilfe von .

Sei die Formel $\alpha$ von

wieder der Form

$\begin{displaymath}\alpha=\bigwedge_{1\leq i\leq k}\left(A_{i,1}\vee A_{i,2}\vee A_{i,3}\right)\end{displaymath}$

Die Matrix

ist nun

Zellen breit und

Zellen hoch, wobei

die Anzahl der unterschiedlichen Literale und

die Anzahl der Klauseln in $\alpha$ 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 kann⁴³:
( $2\cdot j-1$ )te Formel:

$\begin{displaymath}x_{j} + \overline{x_{j}}\geq 1\end{displaymath}$

( $2\cdot j$ )te Formel:

$\begin{displaymath}-x_{j} -\overline{x_{j}}\geq -1\end{displaymath}$
Die letzten Ungleichungen sagen, daß pro Klausel ein Literal wahr sein muß:

$\begin{displaymath}A_{i,1}+A_{i,2}+A_{i,3}\geq 1\end{displaymath}$

Es ist leicht einsichtig, warum dieses

-Problem genau dann auch erfüllt ist, wenn die

von

auch erfüllt ist.

Weitere NPC-Beweise

Weitere NPC-Beweise findet man in der Fachliteratur.

Fußnoten

... folgendermaßen ³⁵: op ist ein Operator also entweder $\vee$ oder $\wedge$
... Beispiel ³⁶: Dies steht auf Seite 944 im Cormen: Introduction to Algorithms
... haben ³⁷: Wenn wir weniger als drei haben, können wir ein weiteres Literal ergänzen, indem wir ein Literal der Klausel verdoppeln.
... reduzieren ³⁸: $SUBSUM\leq_{poly}RP$
... beweisen ³⁹: Wir erstellen einen Algorithmus für mit Hilfe von .
... gleich ⁴⁰: Der zu erzielenden Gewinn für 3 Klauseln und 3 Literale wäre also 444111 (In Worten: vierhundertvierundvierzigtausendeinhundertundelf)
...⁴¹: Also, wenn wir 3 unterschiedliche Literale haben ( $x_{1},x_{2},x_{3}$ ), dann haben wir $4\cdot 3=12$ Gewinne
... sind ⁴²: D.h. Maskierung der Zeilen in der Matrix mit dem Vektor x. Nur dort wo eine 1 vorkommt, wird auch die Spalte genommen.
... kann ⁴³: $x_{j}$ und $\overline{x_{j}}$ können, wie man an den Formeln sieht nicht gleichzeitig oder sein, sondern müssen paarweise verschieden sein.