TIB: NP-Vollständige Probleme (Lernziele KE4 1/2, Update 2)

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 4x4 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.

steine

 

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 4x4 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.

felder

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.


Sie können zum Ende springen und ein Kommentar hinterlassen. Pingen ist im Augenblick nicht erlaubt.





 

4 Kommentare zu “TIB: NP-Vollständige Probleme (Lernziele KE4 1/2, Update 2)”

  1. Barbara Honold
    Mai 23rd, 2013 09:03
    1

    Danke für die anschaulichen Beispiele zum 2D-Domino!

    Eine Frage: Oben bei der Beschreibung der Steine sieht es so aus, als meintest Du, die Steine könnten nur die Farben schwarz und weiß haben. Meintest Du das so, oder war das nur als konkretes Beispiel gedacht?

    Falls es allgemein gedacht war: Ich meine, dass die Steine sehr viele Farben haben können, keineswegs nur schwarz und weiß, und insgesamt gibt es weit mehr als 2^16 mögliche Steine.

    Jede Farbe wird dargestellt durch ein ganzes _Wort_ aus Nullen und Einsen, nicht nur durch je eine Eins oder Null. Dies verrät die Angabe, wonach für die Spielsteine gilt: S ist Untermenge von ({0,1})^+)^4. Dabei bedeutet {0,1}^+, dass wir außer epsilon, dem leeren Wort, beliebige Wörter über {0, 1}^∗ bilden dürfen.

  2. Barbara Honold
    Mai 23rd, 2013 09:06
    2

    Entschuldigung, 2^4 statt 2^16 hätte es oben in meinem Kommentar heißen sollen (ich kann ihn leider nicht mehr korrigieren). Ich wollte damit sagen:

    Wir hätten weit mehr als 2^4 mögliche Kombinationen für die Steine (weil oben im Text 2^4 steht).

  3. Anton
    Mai 23rd, 2013 09:12
    3

    Das war eig. nur ein konkretes Beispiel. Da wir neben der Markierung auch noch die Farben codieren müssen, war mir das zuviel. Aus diesem Grund habe ich mich nur für die Markierung entschieden. Die müsste ja anschaulich genug sein.

    Du hast aber Recht, beim erneuten Durchlesen, ist das nicht mehr so eindeutig, wie von mir zunächst gewünscht. Ich überlege gerade, wie ich das am anschaulichsten rüber bringe...

    Ich habe den Beitrag aktualisiert, hoffentlich ist das nun verständlicher. Barbara: Danke (erneut)!

  4. Barbara Honold
    Mai 23rd, 2013 11:22
    4

    Sehr gern geschehen. Super, so, mit der Korrektur, finde ich das sehr gut zu verstehen. Überhaupt (ebenfalls erneut): Tausend Dank für Deine Mühe mit den vielen hilfreichen konkreten Beispielen!

Beitrag kommentieren