Kategorie: Theoretische Informatik

Lernziel 3

Wie ist der Vollständigkeitsbeweis zu \(SAT\)?

\(SAT\) steht für das englische satisfiability. Also ein Erfüllbarkeitsproblem. Es wird gefragt ob eine aussagenlogische Formel erfüllbar ist (erinnert ihr euch an KNF/DNF aus der technischen Informatik? Das hier ist nicht weit weg…).

Da eine Formel nur endlich viele variablen enthält, die nur mit \(1\) und \(0\) belegt werden können, haben wir eine endliche Anzahl an Möglichkeiten. Wenn wir alle durchprobieren, kommen wir (oder nicht) irgendwann dahin, dass die Formel wahr wird. Haben wir \(n\) Variablen, so müssen wir im worst case \(2^n\) Kombinationen betrachten. Damit benötigen wir für \(SAT\) einen Exponentialzeitalgorithmus und diese gelten für die Praxis als unwichtig, steigt der Aufwand für größere \(n\) doch massiv an. Hätten wir zu dem Problem einen Polynomialzeitalgorithmus, sähe die Sache ganz anders aus.

Aber es gibt einen Lichtblick: Wenn wir nicht jede Möglichkeit durchprobieren wollen, kann das Prüfen einer vorgegebenen Lösung für \(SAT\) in Linearzeit erfolgen. Haben wir \(n\) Variablen, so müssen wir sie erst kurz belegen und die Formel dann auswerten. Beides geht jeweils in Linearzeit. Damit haben wir schon einmal den ersten Schritt getan: wir haben eine \(KTM\) angegeben, die die Hilfseingabe (unsere zu prüfende Belegung der \(n\) Variablen) auf wahr oder falsch kontrolliert. Okay, haben wir nicht. Aber wir könnten es mit wenig Aufwand (vielleicht reiche ich so eine \(KTM\) bei Gelegenheit hier nach) tun. Damit ist der erste Schritt vollbraucht \(SAT\in NP\).

Kümmern wir uns nun um den zweiten Schritt, die \(NP\)-Härte. Aber ohne die Abkürzung der Reduktion zu nehmen. Das folgende Beispiel basiert auf dem Buch von Prof. Dr. Dirk W. Hoffmann (oben rechts verlinkt). Die Credits also ausnahmslos an ihn. Und auch wenn ich mich wie eine kaputte Schallplatte anhöre: das Buch ist ein Lifesaver für theoretische Informatik und gehört in jedes IT-Bücherregel, daher absolute Kaufempfehlung. Der Herr gehört unbedingt unterstützt.

Wir müssen hier also beweisen, dass wir ausnahmslos alle Probleme aus \(NP\) auf \(SAT\) reduzieren können. Da wir keines haben, müssen wir uns eins basteln, wo einzusehen ist, dass es alle Probleme aus \(NP\) „widerspiegelt“ und dieses auf \(SAT\) reduzieren. Nehmen wir also ein beliebiges Problem \(L\in NP\) und eine \(TM\) namens \(T\), die das Problem entscheidet. Wir müssen jetzt zeigen, dass wir für jedes Eingabewort \(\omega\) für \(T\) eine Formel \(F\) konstruieren können, für die gilt:

\(T(\omega)\) terminiert im Endzustand \(\Leftrightarrow F(\omega)\) ist erfüllbar.

D.h. nur wenn unsere Maschine mit dem Eingabewort terminiert, so ist auch unsere Formel mit dem gleichen Eingabewort erfüllbar und andersrum. Wir müssen \(F\) in polynomieller Zeit konstruieren. Dazu werden zunächst Variablen eingeführt:

\(B_{i,k,\sigma}=1\) Nach \(i\) Schritten, steht an Position \(k\) das Zeichen \(\sigma\).

\(S_{i,S}=1\) Maschine \(T\) befindet sich nach \(i\) Schritten im Zustand \(S\).

\(P_{i,k}=1\) Maschine \(T\) befindet sich nach \(i\) Schritten auf Bandposition \(k\).

Die Laufzeit der Maschine ist polynomiell durch das Polynom \(p(n)\) beschränkt, denn \(n\) ist die Länge der Eingabe \(\omega\). Die Indizes von \(i,s\) liegen also im Intervall \([0;p(n)]\). Auch bewegt sich der Schreib-Lese-Kopf maximal \(p(n)\) Positionen nach links oder rechts, so dass wir den Bandinhalt auf dem Teilstück \(-p(n),…,p(n)\) betrachten müssen. Der Kopf steht über der Position \(0\). Ausprobiert wird das an der Sprache \(L:=\{\#^n\mid n\in{\mathbb{N}}\}\) mit dem Alphabet \(\Sigma=\{\#\}\).

Diese Sprache wird von einer \(TM\) erkannt, die nur zwei Zustände hat. \(s_0\) wenn das Zeichen auf dem Band eine \(\#\) ist (Eingabewort \(\omega\in L\)) und \(s_1\) wenn es ein \(B\) (Blank) ist. Da die Berechnung hier bereits nach einem Schritt endet, ist die Laufzeit der Maschine \(p(n)=1\). Wir haben also ein „Problem“, dass in polynomieller Zeit durch die \(T\) entschieden werden kann und damit in \(P\) liegt (das \(N\) ist ja nur das Orakeln der Eingabe). Nun müssen wir \(T\) nur noch polynomiell in eine \(SAT\)-Instanz codieren.

Um den Bandzustand, den Zustand der Maschine und die Position des Lesekopfes als eine Formel zu codieren, werden die oben eingeführten Variablen verwendet. Ist z.B. \(B_{0,1,\#}=1\), so befindet sich auf dem Band jetzt auf Position \(1\) das Zeichen \(\#\). Durch die oben gemachten Einschränkungen, haben wir \(12\) verschiedene Bandvariablen, die wir mit \(0\) oder \(1\) belegen können um den Bandzustand zu repräsentieren (\(B\) ist das Blank).

\(B_{0,-1,B},B_{0,-1,\#},B_{1,-1,B},B_{1,-1,\#}\) \(B_{0,1,B},B_{0,1,\#},B_{1,1,B},B_{1,1,\#}\) \(B_{0,0,B},B_{0,0,\#},B_{1,0,\#},B_{1,0,\#}\)

Der Zustand von \(T\) codieren wir mit:

\(S_{0,S_0},S_{0,S_1},S_{1,S_0},S_{1,S_1}\)

Für die Kopfposition haben wir sechs Variablen:

\(P_{0,-1},P_{0,0},P_{0,1}\) \(P_{1,-1},P_{1,0},P_{1,1},\)

Mit diesen Variablen haben wir alle Variablen repräsentiert, die die Maschine \(T\) einnehmen kann. Wenn wir die Maschine also in \(SAT\) abbilden wollen, sieht die Formel \(F\) dann so aus:

\(F=S\wedge R\wedge T\wedge A\)

Was bedeutet es?

\(S\): Startbedingung. Initiale Konfiguration von \(T\). Die Maschine befindet sich in \(s_0\), das Eingabewort \(\omega\) ist auf dem Band, der Rest ist leer und der Kopf befindet sich auf Position \(0\).

\(R\): Randbedingungen, die \(T\) zu jeder zeit erfüllen muss, d.h. \(R=(R_1\wedge R_2\wedge R_3)\) Diese sind:

\(R_1\): Maschine befindet sich zu jedem Zeitpunkt in nur einem Zustand

\(R_2\): Der Schreib-Lese-Kopf befindet sich immer nur an einer Position.

\(R_3\): Es befindet sich nur ein Symbol an jeder Bandstelle zu jedem Zeitpunkt.

\(T\): Transitionsbedingungen. In dieser Teilformel werden die möglichen Konfigurationsübergänge codiert, d.h. \(T=(T_1\wedge T_2\wedge T_3)\) Sie bestehen aus:

\(T_1\): Maschine geht in Folgekonfiuration über.

\(T_2\): Inaktive Maschine, terminiert.

\(T_3\): Bandinhalt wird geändert.

\(A\): Akzeptanzbedingung. Hier wird codiert, dass die \(TM\) das Wort \(\omega\) dann annimmt wenn es im Endzustand anhält. Der Zustand muss in weniger als \(p(n)\) Berechnungsschritten erreicht werden.

Und nun kommt der Spaß an der Sache. Alle Bedingungen können wir als Formel codieren.

Beispiel: nehmen wir an, das Wort \(\omega\) besteht aus \(\#\), d.h. auf dem Band steht \(B\# B\). Die oben in Prosa verfasste Startbedingung, wäre dann:

\(S=S_{0,s_0}\wedge{P_{0,0}}\wedge{B_{0,-1,B}}\wedge{B_{0,0,\#}}\wedge{B_{0,1,B}}\)

In Worten ausgedrückt: Die Maschine befindet sich nach \(0\) Schritten im Zustand \(s_0\) (erste Bedingung), der Lesekopf nach \(0\) Schritten auf Position \(0\) (zweite Bedingung) und auf dem Band steht auf Positionen \(-1,0,1\) eben \(B,\#,B\) (dritte, vierte und fünfte Bedingung). Und wenn das alles stimmt, die Variablen also alle mit einer \(1\) belegt sind, dann evaluiert die Formel \(S\) bei Auswertung zu \(1\). Oh mein Gott! Das ist genau das, was wir für die Maschine \(T\) festgelegt und nun in eine Formel gequetscht haben.

Haben wir z.B. ein leeres Wort \(\epsilon\), d.h. auf dem Band steht \(BBB\), so sieht unsere Startbedingung wie folgt aus:

\(S=S_{0,s_0}\wedge{P_{0,0}}\wedge{B_{0,-1,B}}\wedge{B_{0,0,B}}\wedge{B_{0,1,B}}\)

Gleiches gilt für Rand-, Transitions- und Akzeptanzbedingungen, die wir eben auch als Formel darstellen können. Ist nur alles ziemliche Schreibarbeit. Wenn die alle erfüllt sind, evaluiert auch unsere Gesamtformel \(F\) (siehe oben) zu einer \(1\). Eventuell schreibe ich die kompletten Rand- und Transitionsbedingungen bei Gelegenheit hier nochmal hin.

Wie wir also sehen können, können wir die Bedingungen für eine Maschine \(T\) in eine Formel \(F\) quetschen, die genau das tut, was wir wollen. Wir haben also gezeigt, wie eine \(NTM\) \(T\) polynomiell auf eine aussagenlogische Formel reduziert werden kann, die genau dann erfüllbar ist, wenn \(T\) in einem Endzustand terminiert.

Ein ausführlicher Beweis ist z.B. auch hier zu finden.

Hier entfaltet \(SAT\) seinen Charme: wir können viele Algorithmen auf \(SAT\) zurückführen, indem wir den Ablauf in die Formel hineincodieren und damit das Problem auf \(SAT\) reduzieren. Und was passt hier besser als Beispiel, als \(3SAT\)?

Antwort zum Lernziel: wir codieren eine komplette Aussagenlogische Formel in ein Wort für eine Turingmaschine, deren Laufzeit polynomiell beschränkt ist. Die Maschine terminiert nur wenn die aussagenlogische Formel wahr ist. Es ist leicht einzusehen, dass diese initiale Turingmaschine, also praktisch unser \(NP\)-vollständiges Problem (wo leicht einzusehen ist, dass es tatsächlich in \(NP\) liegt), in polynomzeit durch eine Kontroll-Turingmaschine entschieden werden kann.

In die Eingabe dieser Maschine dieses wird dann die zu prüfende, aussagenlogische \(SAT\)-Formel codiert und von dieser \(KTM\) ebenfalls in Polynomzeit entschieden.

Lernziel 4

Wie führt man eine einfache, polynomielle Reduktion \({}\leq_{pol}\)  aus?

Reduktion von \(SAT\) auf \(3SAT\)

Die Frage bei \(3SAT\) ist:

Gibt es eine erfüllende Bedingung bei \(n\) aussagenlogischen Klauseln mit maximal \(3\) Literalen (atomare Aussage, z.B. \(\neg{A}\) oder \(A\))?

Damit ist \(3SAT\) eine abgeschwächte Form von \(SAT\). Einschränkung ist, dass die Formel für \(3SAT\) in der Konjunktivform (mit \(\wedge\) verknüpft) vorhanden sein muss. Um also zu zeigen, dass \(3SAT\) ebenfalls \(NP\)-hart ist, müssen wir \(SAT\) auf \(3SAT\) polynomiell reduzieren, formal ausgedrückt:

\(SAT\leq_{pol}3SAT\)

Was wir tun müssen, ist also eine allgemeine Formel nehmen und sie so umformen, dass die beliebig viele Klauseln, aber nur drei Literale pro Klausel hat. Das machen wir mit Hilfe von Hilfsvariablen. Haben wir also ein Term in der folgenden Form in KNF mit \(n\) Variablen:

\((\upsilon_{1,1}\vee\upsilon_{1,2}\vee …\vee\upsilon_{1,n})\wedge(\upsilon_{m,1}\vee\upsilon_{m,2}…\vee\upsilon_{m,n_{m}})\)

Für jede Klausel mit \(n\) Variablen entstehen \(n-2\) neue Klauseln mit \(n-3\) neuen Variablen:

\((\upsilon_{1,1}\vee\upsilon_{1,2}\vee a_{1,1})\wedge(\overline{a_{1,1}}\vee\upsilon_{1,3}\vee a_{1,2})\wedge …\wedge(\overline{a_{1,n-3}}\vee \epsilon_{1,n_{1}-1}\vee\epsilon_{1,n_{1}})\)

Hilfsvariablen? Ja, Hilfsvariablen. Diese Variablen zeigen uns an, welcher Teil aus der zerteilen Klausel das ganze Konstrukt hat wahr werden lassen.

Beispiel? Klar: \((A\vee\overline{B}\vee C\vee\overline{D})\wedge(E\vee F\vee G)\)

Die erste Klausel wandeln wir also um in \(2\) Klauseln mit einer neuen Variable. Die zweite Klauseln können wir so lassen, da wir da bereits drei Literale drin haben. Nennen wir unsere neue Hilfsvariable also einfach \(h_1\). Damit sehen unsere beiden neuen Klauseln nun so aus:

\((A\vee\overline{B}\vee h_1)\wedge(C\vee\overline{D}\vee\overline{h_1})\)

Der Trick hierbei ist, dass die Hilfsvariable \(h_1\) dann falsch wird, wenn die erste Teilklausel wahr wird und wahr wird wenn die zweite Teilklausel wahr wird. Stellen wir doch eine kleine Wertetabelle für den umgeformten Term zusammen, wie wir das auch in der technischen Informatik (Computersysteme 1&2) gemacht haben:

Ich habe Excel etwas vergewaltigt, nehmt mir das nicht übel. Die Spalten haben folgende Bedeutung:

• In den Spalten A-D stehen alle unsere Variablenbelegungen \(A,B,C,D\).
• In Spalte E steht die umzuformende Klausel \((A\vee\overline{B}\vee C\vee\overline{D})\).
• In Spalte F steht die so entstandene erste Teiltklausel,
• In G die zweite.
• In Spalte H steht unsere Hilfsvariable \(h_1\), die falsch wird wenn die erste Teilklausel in Spalte F wahr ist und wahr wird wenn die zweite Teilklausel in Spalte G wahr wird. Der Inhalt von \(h_1\) spielt keine Rolle wenn die Klausel sowieso negativ werden würde (grünes Kästchen).
• In Spalte I und J stehen unsere neuen Teilklausen mit der Hilfsvariable, die wir dann verwenden um die alte Klausel zu repräsentieren.
• Spalte K beherbergt dann beide Klauseln aus I und J mit einem \(\wedge\) verknüpft. Genau diese Klausel
• in Spalte K ist dann: \(((A\vee\overline{B}\vee h_1)\wedge(C\vee\overline{D}\vee\overline{h_1})\)

Und sie tut genau das gleiche wie die initiale Klausel aus den vier Literalen, die wir umformen wollten: \((A\vee\overline{B}\vee C\vee\overline{D})\). Lange Rede, kurzer Sinn:

\((A\vee\overline{B}\vee C\vee\overline{D})\) \(\Leftrightarrow\) \(((A\vee\overline{B}\vee h_1)\wedge(C\vee\overline{D}\vee\overline{h_1})\)

Klauseln mit nur einem Literal bekommen zwei Hilfsvariablen, Klauseln mit zwei Literalen eine, Klauseln mit drei Literalen werden nicht angefasst und Klauseln mit mehr als drei Literalen werden nach dieser Vorgehensweise rekursiv in Klauseln mit drei Literalen umgewandelt. Die Anzahl der Literale hat sich also nur linear erhöht und wir haben einen Weg gefunden \(SAT\) auf \(3SAT\) in Polynomzeit zu reduzieren. Nun können wir auch \(3SAT\) für andere Schweinereien benutzen!

Antwort zum Lernziel: am beispiel von \(3SAT\) sehen wir die Reduktion, indem wir eine aussagenlogische Formel so umformen, dass wir zwar beliebig viele Klauseln, aber nur drei Literale pro Klausel haben. Schaffen wir diese Reduktion in Polynomzeit durchzuführen, so ist sie uns gelungen.

Lernziel 5

Angabe einiger NP-vollständigen Probleme

Im Skript werden noch weitere Probleme besprochen, die \(NP\)-vollständig sind. Zwei davon sind \(CLIQUE\) und \(IND\_SET\). Fangen wir doch zunächst mit \(CLIQUE\) an. Definition (erneut geklaut aus dem Buch von Hr. Hoffmann):

Graph \(G\) mit Knotenmenge \(V\) und Kantenmente \(E\)

Fragestellung: Existieren \(n\) Knoten \(v_1,…,v_n\), die paarweise durch eine Kante aus \(E\) verbunden sind?

Menge \(C=\{v_1,…,v_n\}\) mit dieser Eigenschaft heißt \(CLIQUE\) der Größe \(n\)

In klaren Worten ist eine \(CLIQUE\) eine Menge von Knoten, die alle miteinander verbunden sind.

Beispiel: \(G_1\) mit

\(V_1=\{1,2,3,4,5,6\}\) und

\(E=\{\{1,2\},\{1,3\},\{2,3\},\{2,4\},\{2,5\},\{4,5\},\{5,6\},\{6,3\},…\}\) (die Kanten in die andere Richtung habe ich aus Faulheit ausgelassen, denkt sie euch einfach dazu)

Hier haben wir Cliquen mit den Knoten \(\{1,2,3\},\{2,4,5\},\{2,3,5\},\{3,5,6\}\) identifiziert. Um zu beweisen, dass wir eine Clique der Größe \(n\) gefunden haben, müssen wir nur eine geeignete Knotenmenge raten und prüfen ob paarweise durch eine Kante verbunden sind. Raten wir z.B. \(C=\{1,5,6\}\), müssen wir auf folgende Kanten prüfen: \(\{1,5\},\{1,6\},\{5,1\},\{5,6\},\{6,1\},\{6,5\}\). Jaja, ungerichteter Graph, ich weiß: ein vorhandener Weg von \(A\) nach \(B\) impliziert den Weg von \(B\) nach \(A\). Aber wir tun uns mit der Prüfung aller Möglichkeiten nicht weh, da dieser sowieso polynomiell beschränkt bleibt. So können wir aber auch ungerichtete Graphen in die Betrachtung mit einbeziehen.

Liegen die Kanten also in unserer Menge \(E\), so haben wir eine Clique gefunden. Man sieht leicht, dass mit der zu suchenden Cliquen-Größe der Aufwand, d.h. die Anzahl der zu prüfenden Kanten, quadratisch (\(n^2\)) in Abhängigkeit von \(n\) zunimmt. Da wir eine Lösung raten und sie mit quadratischem Aufwand prüfen können, liegt unsere \(CLIQUE\in NP\) .

Jetzt kümmern wir uns um den aufwendigeren Teil, die \(NP\)-Härte von \(CLIQUE\). Dazu reduzieren wir einfach \(3SAT\) auf \(CLIQUE\). Wir müssen also eine Formel \(M\) konstruieren, dass gilt:

\(M\) ist erfüllbar \(\Leftrightarrow G\) enthält eine Clique der Größe \(n\)

Achtung: wir verfolgen den Weg von einer Formel zum Graphen und nicht anders herum. Wir überführen also eine Formel, die wahr wird wenn sie eine Belegung hat in einen Graphen, der genau bei dieser Belegung eine Clique hat. Machen wir das am besten an einem Beispiel:

Beispiel: \((A)\vee(\neg{A}\wedge{B})\vee(\neg{A}\wedge{C})\)

Wie basteln wir uns daraus einen Graphen? Nach folgenden Regeln:

• Jedes Literal wird ein Knoten
• Zwischen jedem Knoten gibt es eine Kante wenn
  • sie nicht in der selben Klausel stehen und
  • wenn sie gleichzeitig erfüllbar sind (\(A\) und \(\neg{A}\) sind z.B. nicht gleichzeitig erfüllbar)

Ganz einfach. Um es deutlicher zu machen, beschriften wir die Knoten mit \(i,j\). \(i\) ist die Nr. der Klausel und \(j\) die Nummer des Literals in der Klausel. Z.B. wäre der Knoten, der das Literal \(A\) in der ersten Klausel beschreibt, beschriftet mit \((1,1)\).

 

Mit den Knoten können wir auch direkt eine Belegung für die Formel ableiten, die sie wahr werden lässt: \(A=B=C=1\). Wäre ein Knoten negativ, so würden wir das Literal \({}=0\) setzen. Probiert es mal selbst an der folgenden Wertetabelle aus und bastelt euch eine Formel und den dazugehörigen Graphen

Übung:

[spoiler]  „TIB: NP-Vollständige Probleme (Lernziele KE4 2/2, Update)“ weiterlesen

Update: Antworten zu den Lernzielen hinzugefügt.

Nach dieser Kurseinheit haben wir mehr als die Hälfte des Weges geschafft und das Licht am Ende des Tunnels ist schon sichtbar. Hoffen wir, dass es kein Zug ist.

Die Grundlagen des Beweises der Vollständigkeit einer Menge haben wir bereits in diesem Beitrag skizziert. Dass der Beweis nicht unbedingt schwierig ist wenn bereits ein Problem als \(NP\)-vollständig bewiesen ist und wir eine Reduktion durchführen können, haben wir bereits gelernt. Schwieriger ist es jedoch die \(NP\)-Vollständigkeit ohne diese Reduktion von einer bereits bekannten Menge zu beweisen. Wir wenden uns in diesem Beitrag den zwei Problemen aus dem Skript zu und tun dies.

Lernziel 1

Wie ist der Vollständigkeitsbeweis zu 2D-DOMINO?

Bevor diese Frage beantworten: Was ist \(2D-Domino\)? Es wird auch als Kachelproblem bezeichnet. Unter diesem Namen findet sich auch in der Literatur eine Erklärung, wer mit der Beschreibung aus dem Skript nicht weiterkommt. Im Grunde geht es um die vollständige Belegung des Spielbretts nach bestimmten Regeln. Aber fangen wir erstmal klein an und zerlegen die Definition aus dem Skript:

\(N\in\mathbb{N}\)

Das ist die Größe des quadratischen Brettes. Ist \(N := 4\), so ist unser Spielbrett \(4×4\) Felder groß.

\(S\subseteq{({\{0,1\}}^{+})}^4\)

Damit bezeichnen wir den Satz unserer Spielsteine. Ein Spielstein ist gegeben durch ein Quintupel: \((L,R,O,U)\in{({\{0,1\}}^{+})}^4\). Nehmen wir an, dass wir z.B. \(S=\{\{0,0,0,0\},\{0,0,0,1\}\}\) als Steinsatz haben, so befinden sich in unserem Satz zwei Steine: einer hat gar keine Markierung und einer nur unten (siehe nächste Abbildung).

Update: Barbara hat mich hier auf etwas hingewiesen. \((L,R,O,U)\in{({\{0,1\}}^{+})}^4\) bedeutet, dass wir \(L,R,O,U\) als Worte über \({\{0,1\}}^{+}\) codieren können. D.h. wir können z.B. auch einen einzelnen Stein mit \(\{1011,1111,1000,0001\}\) abbilden. Die einzelnen Elemente für \(L,R,O,U\) bezeichnen dann die Farbe links, rechts, oben oder unten im Stein. Bei einem Wort mit der Länge \(4\) haben wir somit \(2^4=16\) verschiedene Farben, die wir nutzen können.

Bei \(4\) Feldern auf dem Stein, die jeweils mit \(16\) unterschiedlichen Farben codiert werden können, haben wir also \(16^4=65536\) unterschiedliche Möglichkeiten einen Stein zu codieren.

Ich bin aber eine faule Sau und habe nur die Farben Schwarz und Weiß zugelassen um eine kleinere Menge an Steinen zu haben. Das habe ich nicht so konkret aufgeführt, wie ich das eig. gedacht habe. Dem Beispiel tut das aber keinen Abbruch. Daher schränke ich für mein Beispiel die Menge der Steine hier (im Gegensatz zum Skript, bitte daher also nicht vergessen: im Skript sind die Farben codiert mittels einem Wort über \({\{0,1\}}^{+}\)) ein auf: \((L,R,O,U)\in({\{0,1\}}^{1})^4\)

Die folgende Abbildung zeigt alle \(2^4\) Möglichkeiten für die Belegung der Steine, d.h. wir haben insg. 16 Steine in unserer Menge \(S\).

 

Kommen wir zur Anfangsbelegung:

\(\alpha: \{1,…,N\}^2\rightarrow S\cup\{\varepsilon\}\)

Mit \(\alpha\) bezeichnen wir die Anfangsbelegung eines Feldes auf dem Brett. Hat unser \(4×4\) Brett z.B. die ersten Beiden Felder mit einem vollständig weißen und einem vollständig schwarzen Stein belegt, während alle anderen leer sind, so wäre \(\alpha(1,1) = (0,0,0,0)\), \(\alpha(1,2) = (1,1,1,1)\) und der Rest der Felder \({}=\varepsilon\). Das alles kommt in unser \(D\), d.h. als \(D\) bezeichnen wir das gesamte Spiel mit: \(D = (N,S,\alpha)\).

\(\beta: \{1,…,N\}^2\rightarrow S\)

Hier haben wir eine konkrete Belegung eines Feldes. Bitte beachten, dass die Belegung das leere Feld \(\varepsilon\) nicht mehr mit einschließt. \(D\) ist lösbar wenn wir die Anfangsbelegung auf dem Feld belassen und die restlichen leeren Felder nach folgenden Regeln belegen:

\((\beta(i,j) = (l,r,o,u)\land\beta(i,j+1) = (l^{‚},r^{‚},o^{‚},u^{‚}))\Rightarrow r=l^{‚}\) und

\((\beta(i,j) = (l,r,o,u)\land\beta(i+1,j) = (l^{‚},r^{‚},o^{‚},u^{‚}))\Rightarrow u=o^{‚}\)

Kleiner Klopper. Sagt aber nichts anderes aus, als dass zwei Steine zueinander passen müssen. Der linke und rechte Stein müssen bei der jeweils zueinander liegenden Seite eine Markierung aufweisen. Das Gleiche gilt für den oberen und unteren Stein. Beispiel? Klar doch.

Wir sehen hier zwei Spielfelder mit \(N=3\). Das 1. Spielfeld hat die Belegung:

\(\beta(1,2) = (1,0,0,0)\), \(\beta(1,3) = (0,1,0,1)\) und \(\beta(2,3) = (1,1,1,0)\). Folgt daraus, dass \(r=l^{‚}\) und \(u=o‘\) wie oben angegeben? Versuchen wir es:

\((\beta(1,2) = (1,0,0,0)\land\beta(1,3) = (0,1,0,1))\Rightarrow 0=0\) und

\((\beta(1,3) = (0,1,0,1)\land\beta(2,3) = (1,1,1,0))\Rightarrow 1=1\)

Sieht gut aus. Nun für Spielbrett Nr. 2 mit Belegung: \(\beta(1,2) = (1,0,0,0)\), \(\beta(1,3) = (1,1,0,0)\) und \(\beta(2,3) = (1,1,1,0)\)

\((\beta(1,2) = (1,0,0,0)\land\beta(1,3) = (1,1,0,0))\Rightarrow 0=1\) und

\((\beta(1,3) = (1,1,0,0)\land\beta(2,3) = (1,1,1,0))\Rightarrow 0=1\)

Ne, hier klappt das leider nicht. Damit ist die angegebene Belegung bei Spielbrett 2 nicht zulässig. Das war es auch schon. Klingt spannend. Wollt Ihr das mal spielen? Bitte sehr: Tetravex. Zumindest ist das Browsergame unserem sehr ähnlich. Nur sind hier die Steine (die Menge \(S\)) hier vorgegeben und nicht nur eine Zeile des Bretts belegt.

Fragestellung: Wir suchen daher nach einer korrekten Belegung für ein Spielbrett. Es ist schnell einzusehen, dass das Spiel in \(NP\) liegt: wir können eine Codierung angeben und diese dann in polynimieller Zeit auf Korrektheit testen. Dazu müssen wir nur eine Kontrollturingmaschine (\(KTM\)) angeben, die eine von uns gegebene Hilfseingabe auf Richtigkeit testet. Um die Belegung zu raten, verwenden wir eine \(NTM\).

Der Beweis der \(NP\)-Vollständigkeit des Dominospiels

Wir haben hier zwei Dinge zu zeigen: \(2D-DOMINO\in NP\) und anschließend die \(NP\)-Härte indem wir ein vollständiges Problem aus \(NP\) auf unseres reduzieren. Haben wir keines, so müssen wir den mühsamen Weg selbst gehen und verzichten auf die Reduktion und beweisen die \(NP\)-Härte direkt. Aber kümmern wir uns zunächst um Punkt 1: \(2D-DOMINO\in NP\). Dazu reicht es eine \(KTM\) (oder \(NTM\)) anzugeben, die eine Hilfseingabe in Polynomzeit auf Korrektheit prüft (eine \(NTM\) rät diese Hilfseingabe auch noch von alleine).

Um eine \(NTM\) anzugeben, müssen wir zunächst das Spiel so formalisieren dass wir die Anfangsbelegung und unsere Steinchen auf das Eingabeband codieren. Die Menge \(S\) der Spielsteine wird lexikographisch nummeriert und damit das ganze Spiel \(D\) durch ein Wort \(x\) über \(\{0,1,\#\}^{*}\) auf das Eingabeband geschrieben.

Ein Beispiel wäre hilfreich: Nehmen wir z.B. das Spielbrett Nr. 1 von oben als Anfangsbelegung und basteln und daraus das gesamte Spiel \(D_1\):

\(\alpha(1,2) = (1,0,0,0)\), \(\alpha(1,3) = (0,1,0,1)\) und \(\alpha(2,3) = (1,1,1,0)\), alle anderen Felder sind leer

So haben das folgende Wort auf unserer \(KTM\) (ich habe aus Faulheit nicht alle 16 Spielsteine auf das Band codiert, sondern nur den ersten \(000\) und letzten \(1111\), dazwischen mit Punkten \(…\) gearbeitet):

\(\gamma D(D_1) = 0\#0\#0\#0\#…\#1\#1\#1\#1\#\#\varepsilon\#1\#0\#0\#0\#0\#1\#0\#1\#\varepsilon\#\varepsilon\#1\#1\#1\#0\#\varepsilon\#\varepsilon\#\varepsilon\)

Zunächst codieren wir also alle 16 Möglichkeiten der Steine, d.h. den Steinsatz auf das Band. Anschließend kommt die Anfangsbelegung \(\alpha\) des Bretts, nachdem wir sie mit \(\#\#\) von dem auf dem Band ebenfalls codierten Steinsatz getrennt haben. Nicht vergessen: mit \(\varepsilon\) werden leere Felder bezeichnet.

Die Menge aller lösbaren Belegungen nennen wir:

\(2D-DOMINO = \{x\in\{0,1,\#\}^{*}\mid x\in Bild(\gamma D)\) und \({\gamma D}^{-1}(x)\) ist lösbar \(\}\).

Aufdröseln: \(2D-DOMINO\) besteht also aus dem Wort \(x\) über dem Alphabet \(\{0,1,\#\}^{*}\), wobei \(x\) ein Bild von \(\gamma D\) und die Inverse von \(\gamma D(x)\) lösbar sein muss. \(\gamma D\) ist unsere Funktion, die als Parameter unser komplettes Spiel \(D\) (Spielbrettgräße, Steine, Anfangsbelegung) als Wort bekommt und uns dazu das \(x\) (das Spiel \(D\) als codiertes Wort) ausgibt. Damit ist \(D\) unser Definitionsbereich für die Funktion \(\gamma D\) und \(x\) liegt im Bildbereich von \(\gamma D\). Wenn nun auch noch das Spiel \(D\) lösbar ist (nicht jede Initialbelegung auf dem Spielbrett hat eine Lösung), so gehört das zum Spiel \(D\) codierte Wort zur Menge \(2D-DOMINO\). Anhand unseres Beispiels von Spielbrett Nr. 1 haben wir zusammengefasst:

\(D_1 = (N,S,\alpha)\) (unser Spiel)

\(S = \{\{0,0,0,0\}, \{0,0,0,1\}, …,\{1,1,1,1\}\}\) (unsere Spielsteine)

\(\alpha(1,2) = (1,0,0,0)\), \(\alpha(1,3) = (0,1,0,1)\) und \(\alpha(2,3) = (1,1,1,0)\) (unsere Anfangsbelegung)

\(\gamma D(D_1) = 0\#0\#0\#0\#…\#1\#1\#1\#1\#\#\varepsilon\#1\#0\#0\#0\#0\#1\#0\#1\#\varepsilon\#\varepsilon\#1\#1\#1\#0\#\varepsilon\#\varepsilon\#\varepsilon\) (unser Spiel als codiertes Wort \(x\))

\(x\in Bild(\gamma D(D_1))\) (das Wort ist, wie man oben sehen kann im Bildbereich der Funktion \(\gamma D\)) und

\(\gamma D^{-1}(x) = D_1)\) (die Inverse \(\gamma D^{-1}\) gibt uns zu jedem \(x\) ein \(D\) zurück, d.h. zu jedem Codewort das zugehörige Spiel. Und das Spiel ist lösbar. Es gibt also eine vollständige Belegung \(\beta\) für das Spiel \(D_1\), die die oben genannten Regeln nicht verletzt).

Bitte beachtet, dass hier das ganze Spiel \(D\) ohne zu testende Belegung auf das Band codiert wird. Die zu testende Belegung ist unsere Hilfseingabe \(\beta\). Codieren wir also unser Spiel \(D\) zusammen mit unserer zu testenden Hilfseingabe \(\beta\) auf das Band, so können wir anhand der Regeln in quadratischer Zeit prüfen ob \(\beta\) eine Lösung für \(D\) ist.

Damit ist die Menge \(2D-DOMINO\in NP\).

Bitte beachten: im Gegensatz zum vorherigen Beitrag zu KE3 haben wir hier zuerst die Zugehörigkeit von \(2D-DOMINO\) zur \(NP\) gezeigt indem wir eine \(KTM\) angegeben haben, die mit unserem codierten Wort auf dem Eingabeband und unserer zu testenden Hilfseingabe diese Lösung überprüft. Nun müssen wir für die Vollständigkeit noch \(2D-DOMINO\) ist \(NP\)-hart zeigen (ich Wiederhole mich häufig, was die Kriterien für die Vollständigkeit betrifft, aber besser zu viel als zu wenig).

Dazu zeigen wir, dass alle Mengen aus \(M\in NP\) auf unsere Problemmenge \(2D-DOMINO\) in polynomieller Zeit reduzieren lassen, formal ausgedrückt:

\({M}\leq_{pol} 2D-DOMINO\)

Denn das ist ja der Charme an der Vollständigkeit: können wir eine vollständige Menge reduzieren, können wir alle reduzieren (für eine Auffrischung, schaut in den letzten Beitrag zu KE3). Sobald das getan ist, gilt die Menge \(2D-DOMINO\) als \(NP\)-vollständig.

Das Prinzip der in der KE4 beschriebenen Probleme ist es zu zeigen, dass man zunächst für alle Mengen \(M\in NP\) diese auf \(2D-DOMINO\) reduziert und dann \(2D-DOMINO\) nutzt um es dann auf das Problem \(SAT\), \(SAT\) dann auf \(3SAT\) usw. zu reduzieren und so die \(NP\)-Vollständigkeit der Probleme zu beweisen. D.h. haben wir eine Menge initial als \(NP\)-Vollständig nachgewiesen, so können wir durch einfache Reduzierung andere Mengen sofort auch als \(NP\)-Vollständig nachweisen (hier sei auf den Abschnitt zu Cook im Beitrag zu KE3 verwiesen).

Zeitbedingt muss ich den Beweis der \(NP\)-Härte für \(2D-DOMINO\) überspringen, werde versuchen ihn für \(SAT\) und \(3SAT\) im nächsten Beitrag nachzuholen, da \(SAT\) doch häufiger anzutreffen ist als \(2D-DOMINO\). Wer eine schöne Beschreibung des Beweises aus dem Skript hat, immer her damit.

Antwort zum Lernziel: zunächst wird wie bei allen Beweisen der Vollständigkeit gezeigt, dass sich \(2D-DOMINO\) in \(NP\) befindet indem man ein Verfahren angibt, dass das Problem in nichtdeterministischer polynomieller Zeit löst, d.h. eine \(KTM\), dass unsere Prüfbelegung (sog. Hilfseingabe) auf Korrektheit prüft. Anschließend zeigt man die \(NP\)-Härte von \(2D-DOMINO\) mittels zwei Möglichkeiten:

1. die leichte: wir reduzieren \(2D-DOMINO\) polynomiell auf ein bekanntes, \(NP\)-schweres Problem indem man ein Verfahren angibt, dass diese Reduktion in polynomieller Zeit schafft oder

2. die schwere: wenn wir kein Problem haben (Henne-Ei-Problem), müssen wir eines angeben, bei dem einzusehen ist, dass es definitiv in \(NP\) liegt (ob es praxistauglich ist, ist egal). Man konstruiert sich sozusagen ein Problem. Auf dieses wird dann \(2D-DOMINO\) reduziert.

Stephen A. Cook hat uns die Arbeit aber abgenommen und \(SAT\) als \(NP\)-vollständig bewiesen, so dass wir die \(NP\)-Vollständigkeit von \(2D-DOMINO\) beweisen könnten wenn wir es auf \(SAT\) zurückführen.

Lernziel 2

Wie beweist man die \(NP\)-Vollständigkeit einer Menge?

Antwort zum Lernziel: Doppelt hält besser: Für die \(NP\)-Vollständigkeit eines Problems müssen wir also zuerst nachweisen, dass es in \(NP\) liegt (dazu geben wir eine \(KTM\) an, die das Problem in Polynomzeit mit einer gegebenen Hilfseingabe entscheiden kann. Oder eine \(NTM\) zum vorherigen Ergebnis-orakeln, denn das orakeln ist das \(N\) in \(NTM\)). Anschließend muss noch die \(NP\)-härte nachgewiesen werden, indem wir ein vollständiges Problem in Polynomzeit auf unseres reduzieren oder auf Reduktion verzichten und die \(NP\)-Härte direkt nachweisen.

Wenn wir also noch kein \(NP\)-vollständiges Problem haben, dass wir reduzieren können, haben wir ein klassisches Henne-Ei-Problem. Zum Glück gibt es kluge Leute, die das auch ohne die Reduzierung geschafft haben. Und sie leben auch noch: einer davon ist Stephen A. Cook mit seinem berühmten Satz von Cook. In diesem zeigte er die Vollständigkeit des \(SAT\)-Problems. Wir wollen den Beweis mal nachvollziehen, so als Kompensation zum fehlenden \(2D-DOMINO\)-Beweis von oben.

Im nächsten Beitrag geht es dann entsprechend um \(SAT\).