Ψ Die Informatikseite

Menü
Unterabschnitte

Einige NP-Vollständigkeitsbeweise

SAT $\leq_{poly}$ 3SAT (lokale Ersetzung)

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ßen35:
$v\leftrightarrow v_{L}\,op\,\,v_{R}$ bedeutet:
$v$ ist 1, wenn $v_{L}\,op\,\,v_{R} \equiv 1$
$v$ 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 Beispiel36 klar machen:
$v$ $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 $v$ 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 haben37. 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 $k$ gibt, wobei $k$ 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 $RP$ genügt es nachzuweisen, daß $SUBSUM \in NPC$, da $SUBSUM$ ein Spezialfall von $RP$ ist. Um $SUBSUM$ auf $RP$ zu reduzieren38 setzen wir das Gewicht für jedes Element gleich 1.
Die Frage von $SUBSUM$ ist es nun:
Gibt es eine Teilmenge aller Elemente mit dem Gewinn $p=q$?
Teil 2:
Es gilt zu beweisen39:

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

Sei die $3SAT$-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 gleich40

\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 $SUBSUM$41:

\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 $true$ und $false$ 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 $1$ bzw. eine $2$ 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 $3SAT$-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 $x$ gibt, dessen Komponenten $0$ oder $1$ sind42, so daß die Gleichung $A\cdot x\geq b$ wahr ist.
  1. 0/1 ILP ist in NP
    Mittel Guess-and-Check-Verfahren läßt sich der Vektor $x$ ermitteln und anschließend überprüfen.
  2. $3SAT \leq_{poly} 0/1-ILP$
    Wir reduzieren $3SAT$ in polynomieller Zeit auf $0/1 ILP$, d.h wir erzeugen für $3SAT$ einen Algorithmus mit Hilfe von $0/1 ILP$.
Sei die Formel $\alpha$ von $3SAT$ 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 $A$ ist nun $2n$ Zellen breit und $2n+k$ Zellen hoch, wobei $n$ die Anzahl der unterschiedlichen Literale und $k$ 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 $1$ für ,,false'' eine $0$.
  • Die ersten $2n$ 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:
    ($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 $k$ 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 $0/1 ILP$-Problem genau dann auch erfüllt ist, wenn die $3KNF$ von $3SAT$ auch erfüllt ist.

Weitere NPC-Beweise

Weitere NPC-Beweise findet man in der Fachliteratur.

Fußnoten

... folgendermaßen35
op ist ein Operator also entweder $\vee$ oder $\wedge$
... 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
$SUBSUM\leq_{poly}RP$
... beweisen39
Wir erstellen einen Algorithmus für $3SAT$ mit Hilfe von $SUBSUM$.
... gleich40
Der zu erzielenden Gewinn für 3 Klauseln und 3 Literale wäre also 444111 (In Worten: vierhundertvierundvierzigtausendeinhundertundelf)
...$SUBSUM$41
Also, wenn wir 3 unterschiedliche Literale haben ( $x_{1},x_{2},x_{3}$), dann haben wir $4\cdot 3=12$ 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
$x_{j}$ und $\overline{x_{j}}$ können, wie man an den Formeln sieht nicht gleichzeitig $1$ oder $0$ sein, sondern müssen paarweise verschieden sein.