Date post: | 05-Apr-2015 |
Category: |
Documents |
Upload: | emeric-leider |
View: | 103 times |
Download: | 0 times |
Planares 3 SAT ist NP-vollständig
Seminar über Algorithmen SS 07 Jale Hayta
Hayta - Planares 3SAT NP-vollständig 2
Gliederung
Beweisidee 3SAT Graph von 3SAT 3SAT G(B)G(B‘) Planares 3SAT Beweis und Beispiel Quellen
Hayta - Planares 3SAT NP-vollständig 3
Beweisidee
3SAT liegt in NP und ist bekanntermassen NP-vollständig.
Hier konkret: 3SAT ≤P P3SAT
Das heißt: NP-Schwerheit muss bewiesen werden.
Hayta - Planares 3SAT NP-vollständig 4
3SAT
Gegeben sind m Klauseln mit n Variablen in konjunktiver Normalform und jede Klausel enthält höchstens 3 Literale
Gegeben sind Boolesche Variablen x1,…,xn . Zu jeder Variablen gibt es 2 mögliche Literale
x und ¬x Alle Klauseln müssen mind. ein wahres Literal
haben, damit die Formel erfüllt ist. 3-SAT ist NP-vollständig.
Hayta - Planares 3SAT NP-vollständig 5
Graph von 3SAT1
Definition: Sei B eine 3SAT Formel. Dann gilt G(B) = (N,A)
N=cj|1 ≤ j ≤ m vi|1 ≤ i ≤ n. A= A1A2,wobei gilt: A1 = ci,vj |vj ci oder vj ci
A2 = vj,vj+1 |1≤ j<n vn,v1
Hayta - Planares 3SAT NP-vollständig 6
Graph von 3SAT2
Gegeben ist eine 3SAT Formel B, zu der es einen Graphen G(B) gibt. Dieser muss nicht unbedingt planar sein (kann aber).
a b c d
Bsp: B=(a+¬b+c)(c+d)
Hayta - Planares 3SAT NP-vollständig 7
3SAT G(B)G(B‘) Planares 3SAT
Das Ziel ist ein G(B) in polynomieller Zeit umzuwandeln in G(B‘) planar, sodass B‘ P3SAT* Formel.
Es muss gelten: B ist erfüllbar B‘ ist erfüllbar.
* P3SAT – Planares 3SAT
Hayta - Planares 3SAT NP-vollständig 8
Beweis und Beispiel1
Hayta - Planares 3SAT NP-vollständig 9
Beweis und Beispiel2
ci
cj
a b
Hier ein kleiner Auszug aus der Grafik zuvor. Das Problem hier ist die Kreuzung der Leitungen.
Hayta - Planares 3SAT NP-vollständig 10
Beweis und Beispiel3
Hier Negationen nicht erkennbar,daher ist eine Spezifikation nötig!
Hayta - Planares 3SAT NP-vollständig 11
Beweis und Beispiel4
Eine Kreuzung wird durch ein Gadget ersetzt. Hilfsvariablen { ,,, ,} und {a1,a2,b1,b2}
werden eingeführt. Annahme laut Graphen:
X ist erfüllbar [a a1], [b b1]
Hayta - Planares 3SAT NP-vollständig 12
Spezifikation zu G(X)
Der Graph G(B) wird durch einen SubgraphenG(X) ersetzt, der wie folgt spezifiziert ist:(a2+b2+) (a2+) (b2+) ,i.e. a2b2 ;(a2+b1+)(a2+)(b1+), i.e. a2b1 ;(a1+b1+)(a1+)(b1+), i.e. a1b1 ;(a1+b2+)(a1+)(b2+), i.e. a1b2 ;(+++); (+) (+) (+) (+); (a2+a) (a+a2)(b2+b) (b+b2), i.e. a a2, b
b2;
Hayta - Planares 3SAT NP-vollständig 13
Spezifikation zu G(X)
Der Graph G(B) wird durch einen SubgraphenG(X) ersetzt, der wie folgt spezifiziert ist:(a2+b2+) (a2+) (b2+) ,i.e. a2b2 ;(a2+b1+)(a2+)(b1+), i.e. a2b1 ;(a1+b1+)(a1+)(b1+), i.e. a1b1 ;(a1+b2+)(a1+)(b2+), i.e. a1b2 ;(+++); (+) (+) (+) (+); (a2+a) (a+a2)(b2+b) (b+b2), i.e. a a2, b
b2;
Hayta - Planares 3SAT NP-vollständig 14
Gadget
Hayta - Planares 3SAT NP-vollständig 15
Gadget2
Hayta - Planares 3SAT NP-vollständig 16
Gadget3
Hayta - Planares 3SAT NP-vollständig 17
Spezifikation von G(X)2
Der Graph G(B) wird durch einen SubgraphenG(X) ersetzt, der wie folgt spezifiziert ist:(a2+b2+) (a2+) (b2+) ,i.e. a2b2 ;(a2+b1+)(a2+)(b1+), i.e. a2b1 ;(a1+b1+)(a1+)(b1+), i.e. a1b1 ;(a1+b2+)(a1+)(b2+), i.e. a1b2 ;(+++); (++)(++ )(+) (+) (+) (+); (a2+a) (a+a2)(b2+b) (b+b2), i.e. a a2, b
b2;
Hayta - Planares 3SAT NP-vollständig 18
Gadget4
Hayta - Planares 3SAT NP-vollständig 19
„”: Gesucht: Wie sind (,,,) in X belegbar?X ist erfüllbar X eine der erfüllbaren Belegungen annimmt.
„“: Gesucht: Belegungen für a und b.a und b müssen Belegungen haben, sodass Xerfüllbar wird.
Beweis
Hayta - Planares 3SAT NP-vollständig 20
Kreuzungsproblem gelöst
C i C i
Beides richtig da offensichtlich gelten muss: a1a
a a 1
Hayta - Planares 3SAT NP-vollständig 21
A= A1A2
Hayta - Planares 3SAT NP-vollständig 22
Beispiel3
Jede Kreuzung wird durch ein Gadget ersetzt.
Die Formel ändert sich, aber durch die Modifikation ändert sich nicht die Erfüllbarkeit. □
Hayta - Planares 3SAT NP-vollständig 23
Bibliographie
D. Lichtenstein; Planar formulae and their uses. SIAM Journal on Computing 11 (1982), 329-343;
D. E. Knuth and A. Raghunathan: The problem of compatible representatives. SIAM Journal on Discrete Mathematics 5 (1992), 422-427.
Hayta - Planares 3SAT NP-vollständig 24
Danke!