Pøevod 3-SAT na ILP
Problém ILP ( eloèíselné lineární programování) Vstup: Celoèíselná mati e A a eloèíselný vektor b . Otázka: Existuje eloèíselný vektor x , takový ¾e Ax b ? Pøíklad instan e problému:
0 A=
3 1 2
2 5 0 1 1 0
1 A
0 b=
8 3 5
1 A
Ptáme se tedy, zda existuje eloèíselné øe¹ení následují í soustavy nerovni : 3x1 2x2 + 5x3 8 x1 + x3 3 2x1 + x2 5
Pøevod 3-SAT na ILP
Jedním z øe¹ení soustavy 3x1
je napøíklad
nebo»
2x2 + 5x3
8
x1 + x3 3 2x1 + x2 5
x1 = 4, x2 = 1, x3 = 1, tj.
0 x =
3 ( 4)
4 1 1
21+51 4+1 2 ( 4) + 1
Pro tuto instan i je tedy odpovìï
1 A
= = =
Ano.
9 3 7
8 5
3
Pøevod 3-SAT na ILP
Vìta Problém ILP je NP-tì¾ký. NP-obtí¾nost problému ILP doká¾eme tak, ¾e uká¾eme polynomiální reduk i z následují ího známého NP-úplného problému: 3-SAT Vstup: Booleovská formule ' v konjunktivní normální formì, kde ka¾dá klauzule obsahuje právì tøi literály. Otázka: Je ' splnitelná?
Pøevod 3-SAT na ILP
Pøedpokládejme, ¾e máme dánu nìjakou konkrétní instan i problému 3-SAT, napøíklad následují í formuli ':
x _:x2 _ x3 ) ^ (x2 _:x3 _ x4) ^ (x1 _:x3 _:x4) ^ (:x1 _:x2 _ x4 )
( 1
Na¹ím úkolem je vyrobit k formuli ' soustavu lineární h nerovni takovou, ¾e tato soustava bude mít øe¹ení v oboru elý h èísel právì tehdy, kdy¾ je formule ' splnitelná.
Pøevod 3-SAT na ILP
x _:x2 _ x3 ) ^ (x2 _:x3 _ x4) ^ (x1 _:x3 _:x4) ^ (:x1 _:x2 _ x4 )
( 1
Krok 1: Ka¾dé booleovské promìnné x ve formuli ' bude v soustavì nerovni odpovídat neznámá x . i
0
i
Napøíklad pro formuli ' uvedenou vý¹e bude soustava nerovni obsahovat neznámé x1 , x2 , x3 , x4 . 0
0
0
0
Pøevod 3-SAT na ILP
x _:x2 _ x3 ) ^ (x2 _:x3 _ x4) ^ (x1 _:x3 _:x4) ^ (:x1 _:x2 _ x4 )
( 1
Krok 2: Nejprve do soustavy pøidáme pro ka¾dou neznámou nerovni x 0 a x 1: 0
0
i
i
x dvoji i 0
i
Pøevod 3-SAT na ILP
x _:x2 _ x3 ) ^ (x2 _:x3 _ x4) ^ (x1 _:x3 _:x4) ^ (:x1 _:x2 _ x4 )
( 1
Krok 2: Nejprve do soustavy pøidáme pro ka¾dou neznámou nerovni x 0 a x 1: 0
0
i
i
x1 x1 x2 x2 0
0
0
0
0 1 0 1
x3 x3 x4 x4 0
0
0
0
0 1 0 1
x dvoji i 0
i
Pøevod 3-SAT na ILP
x _:x2 _ x3 ) ^ (x2 _:x3 _ x4) ^ (x1 _:x3 _:x4) ^ (:x1 _:x2 _ x4 )
( 1
Krok 2: Nejprve do soustavy pøidáme pro ka¾dou neznámou nerovni x 0 a x 1: 0
0
i
i
x1 x1 x2 x2 0
0
0
0
0 1 0 1
x3 x3 x4 x4 0
0
0
0
x dvoji i 0
i
0 1 0 1
Poznámka: Tyto nerovni e zaruèují, ¾e v libovolném øe¹ení výsledné soustavy bude muset pro v¹e hna x platit x 2 f0; 1g. 0
0
i
i
Pøevod 3-SAT na ILP
Krok 3: Pro ka¾dou klauzuli tvaru (L1 _ L2 _ L3 ), kde L jsou jednotlivé literály, pøidáme do soustavy nerovni nerovni i i
f1 + f2 + f3 1 kde
f
i
=
x
0 i
(1
x) 0
i
pokud L pokud L
i
=
i
=
x
:x i
i
Pøevod 3-SAT na ILP
Krok 3: Pro ka¾dou klauzuli tvaru (L1 _ L2 _ L3 ), kde L jsou jednotlivé literály, pøidáme do soustavy nerovni nerovni i i
f1 + f2 + f3 1 kde
f
i
=
x
pokud L pokud L
0 i
(1
x) 0
i
i
=
i
=
x
:x i
i
Pøíklad: Pro klauzuli (x1 _ :x3 _ :x4 ) pøidáme nerovni i
x1 0
+ (1
x3 ) 0
+ (1
x4 ) 1 0
Pøevod 3-SAT na ILP
x _:x2 _ x3 ) ^ (x2 _:x3 _ x4) ^ (x1 _:x3 _:x4) ^ (:x1 _:x2 _ x4 )
( 1
Takto vypadá elá odpovídají í soustava nerovni :
x10 + (1 x20 ) x20 + (1 x30 ) 0 x1 + (1 x30 ) + (1 (1 x10 ) + (1 x20 )
x10 x10 x20 x20 x30 x30 x40 x40 + x30 + x40 x40 ) + x40
0 1 0 1 0 1 0 1 1 1 1 1
Pøevod 3-SAT na ILP
Krok 4: Soustavu nerovni pøevedeme pomo í jednodu hý h aritmeti ký h úprav do po¾adovaného mati ového tvaru tak, aby v¹e hny nerovni e byly tvaru
1 x1 0
kde
+
2 x2 0
+
1 ; 2 ; : : : ; a d jsou konstanty. n
+
x d 0
n
n
Pøevod 3-SAT na ILP
Krok 4: Soustavu nerovni pøevedeme pomo í jednodu hý h aritmeti ký h úprav do po¾adovaného mati ového tvaru tak, aby v¹e hny nerovni e byly tvaru
1 x1 0
kde
+
2 x2 0
+
+
x d 0
n
n
1 ; 2 ; : : : ; a d jsou konstanty. n
Poznámka: Pokud se v nerovni i vyskytuje nerovnost `' místo `', mù¾eme vyu¾ít toho, ¾e x y právì tehdy, kdy¾ x y .
Pøevod 3-SAT na ILP
Pøíklad:
x1 0
+ (1
x3 ) 0
+ (1
x4 ) 1 0
Pøevod 3-SAT na ILP
Pøíklad:
x1 0
+ (1
x1 0
x3 ) + (1 x4 ) 1 x3 x4 + 2 1 0
0
0
0
// seèteme jednotlivé èleny
Pøevod 3-SAT na ILP
Pøíklad:
x1 0
+ (1
x1 0
x3 ) + (1 x4 ) 1 x3 x4 + 2 1 x1 x3 x4 1 0
0
0
0
0
0
0
// seèteme jednotlivé èleny // odeèteme 2 od obou stran
Pøevod 3-SAT na ILP
Pøíklad:
x1 0
+ (1
x1 0
x3 ) + (1 x4 ) x3 x4 + 2 x1 x3 x4 x1 + x3 + x4 0
0
0
0
0
0
0
0
0
0
1 1 1 1
// seèteme jednotlivé èleny // odeèteme 2 od obou stran // vynásobíme obì strany 1
Pøevod 3-SAT na ILP
Pøíklad:
x1 0
x3 ) + (1 x4 ) x3 x4 + 2 x1 x3 x4 x1 + x3 + x4
+ (1
0
x1 0
0
0
0
0
0
0
0
0
0
1 1 1 1
// seèteme jednotlivé èleny // odeèteme 2 od obou stran // vynásobíme obì strany 1
Po doplnìní hybìjí í h èlenù (s koe ienty 0) tedy výsledná nerovni e vypadá takto: (
1) x1 0
+
0 x2 0
+
1 x3 0
+
1 x4 0
1
Pøevod 3-SAT na ILP
x _:x2 _ x3 ) ^ (x2 _:x3 _ x4) ^ (x1 _:x3 _:x4) ^ (:x1 _:x2 _ x4 )
( 1
Po úpravì v¹e h nerovni tedy dostaneme soustavu: (
( (
1) x10 1 x10 0 x10 0 x10 0 x10 0 x10 0 x10 0 x10 1) x10 0 x10 1) x10 1 x10
+ + +
(
+ + + + + + + + +
(
0 x20 0 x20 1) x20 1 x20 0 x20 0 x20 0 x20 0 x20 1 x20 1) x20 0 x20 1 x20
+ + + + +
(
+ + + + + + +
(
0 x30 0 x30 0 x30 0 x30 1) x30 1 x30 0 x30 0 x30 1) x30 1 x30 1 x30 0 x30
+ + + + + + +
(
+ + +
(
+ +
(
0 x40 0 x40 0 x40 0 x40 0 x40 0 x40 1) x40 1 x40 0 x40 1) x40 1 x40 1) x40
0 1 0 1 0 1 0 1 0 0 1 1
Pøevod 3-SAT na ILP
x _:x2 _ x3 ) ^ (x2 _:x3 _ x4) ^ (x1 _:x3 _:x4) ^ (:x1 _:x2 _ x4 )
( 1
Tuto soustavu mù¾eme zapsat mati ovým zápisem jako:
0 B B B B B B B B B B B B B B B B B B
1 1 0 0 0 0 0 0 1 0 1 1
0 0 1 1 0 0 0 0 1 1 0 1
0 0 0 0 1 1 0 0 1 1 1 0
0 0 0 0 0 0 1 1 0 1 1 1
1 CC CC CC 0 CC x CC BB x21 CC x3 CC x4 CC CC A 0
0
0
0
001 BB 1 CC BB 0 CC 1 BBB 10 CCC CC BBB 1 CCC A BB 0 CC BB 1 CC BB 0 CC BB 0 CC 1A 1
Pøevod 3-SAT na ILP
Je zøejmé, ¾e tuto konstruk i mù¾eme provést v èase je velikost formule '.
O (n2 ), kde n
Poznámka: Ve skuteènosti nejví e èasu zabere vyplòování mati e A nulami. Není tì¾ké ovìøit, ¾e v¹e ostatní (vyplnìní nenulový h prvkù v mati i A a vytvoøení vektoru b ) je mo¾né provést v èase O (n).
Pøevod 3-SAT na ILP
Je zøejmé, ¾e tuto konstruk i mù¾eme provést v èase je velikost formule '.
O (n2 ), kde n
Poznámka: Ve skuteènosti nejví e èasu zabere vyplòování mati e A nulami. Není tì¾ké ovìøit, ¾e v¹e ostatní (vyplnìní nenulový h prvkù v mati i A a vytvoøení vektoru b ) je mo¾né provést v èase O (n). Poznámka: Není tì¾ké si rozmyslet, jak by vypadal algoritmus, který by vytváøel mati i A a vektor b pøímo, bez mezikroku s úpravami nerovni . Tento mezikrok zavádíme pro lep¹í po hopení konstruk e.
Pøevod 3-SAT na ILP
Nyní je¹tì zbývá ukázat korektnost konstruk e. Nejprve si v¹imnìme, ¾e vzhledem k tomu, ¾e vytvoøená soustava obsahuje pro ka¾dé x nerovni e 0
i
x 0
x 1
0
0
i
i
musí jakékoliv øe¹ení elé soustavy (pokud vùbe nìjaké existuje) být toho typu, ¾e jednotlivá x nabývají pouze hodnot 0 nebo 1. 0
i
Pøevod 3-SAT na ILP
Ka¾dému ohodno ení booleovský h promìnný h x1 ; x2 ; : : : ; x ve formuli ' jednoznaènì odpovídá pøiøazení hodnot neznámým x1 ; x2 ; : : : ; x ve vytvoøené soustavì nerovni : k
0
0
0
k
x
0
i
=
0 1
kdy¾ [x ℄ kdy¾ [x ℄ i
=
i
=
false true
Pøevod 3-SAT na ILP
Ka¾dému ohodno ení booleovský h promìnný h x1 ; x2 ; : : : ; x ve formuli ' jednoznaènì odpovídá pøiøazení hodnot neznámým x1 ; x2 ; : : : ; x ve vytvoøené soustavì nerovni : k
0
0
0
k
x
0
i
=
0 1
kdy¾ [x ℄ kdy¾ [x ℄ i
=
i
=
false true
Tento vztah je vzájemnì jednoznaèný. Ke ka¾dému pøiøazení eloèíselný h hodnot neznámým x1 ; x2 ; : : : ; x takovému, ¾e pro v¹e hna x platí x 2 f0; 1g, existuje odpovídají í pøiøazení booleovský h hodnot . 0
0
0
0
0
k
i
i
Pøevod 3-SAT na ILP
Vezmìme si nyní nìjaké ohodno ení booleovský h promìnný h a jemu odpovídají í pøiøazení hodnot 0 a 1 neznámým x1 ; x2 ; : : : ; x . 0
0
0
k
Pøipomeòme, ¾e ve vytvoøené soustavì nerovni odpovídá ka¾dé klauzuli (L1 _ L2 _ L3 ) vyskytují í se ve formuli ' nerovni e tvaru
f1 + f2 + f3 1 kde
f je tvaru x , pokud L 0
i
j
i
=
x , nebo (1 x ), pokud L 0
j
j
i
=
:x . j
Pøevod 3-SAT na ILP
Vezmìme si nyní nìjaké ohodno ení booleovský h promìnný h a jemu odpovídají í pøiøazení hodnot 0 a 1 neznámým x1 ; x2 ; : : : ; x . 0
0
0
k
Pøipomeòme, ¾e ve vytvoøené soustavì nerovni odpovídá ka¾dé klauzuli (L1 _ L2 _ L3 ) vyskytují í se ve formuli ' nerovni e tvaru
f1 + f2 + f3 1 kde
f je tvaru x , pokud L 0
i
j
=
i
x , nebo (1 x ), pokud L 0
j
Vidíme, ¾e a» u¾ je literál L tvaru f = 1, pokud [L ℄ = true f = 0, pokud [L ℄ = false i
i
i
i
i
j
x nebo :x , platí, ¾e: j
j
i
=
:x . j
Pøevod 3-SAT na ILP
Hodnota výrazu f1 + f2 + f3 pøi daném pøiøazení je tedy poètem literálù v klauzuli (L1 _ L2 _ L3 ), které mají pøi ohodno ení hodnotu true. Vzhledem k tomu, ¾e [L1 _ L2 _ L3 ℄ = true právì tehdy, kdy¾ pro alespoò jeden z literálù L1 ; L2 ; L3 platí [L ℄ = true, je oèividné, ¾e nerovnost f1 + f2 + f3 1 i
platí pøi daném pøiøazení právì tehdy, kdy¾
L _ L2 _ L3 ℄ = true :
[ 1
Pøevod 3-SAT na ILP
Tvrzení Pokud je formule ' splnitelná, pak existuje eloèíselné øe¹ení vytvoøené soustavy nerovni .
Dùkaz: Jestli¾e je ' splnitelná, existuje nìjaké ohodno ení takové, ¾e ['℄ = true, tj. takové, kde [C ℄ = true pro v¹e hny klauzule C formule '. i
i
Z pøed hozího je zøejmé, ¾e pokud vezmeme jemu odpovídají í pøiøazení hodnot 0 a 1 neznámým x1 ; x2 ; : : : ; x , budou pøi tomto pøiøazení platit v¹e hny vytvoøené nerovni e: 0
0
0
k
Nerovni e tvaru x 0 a x 1 proto, ¾e x 2 f0; 1g. Nerovni e odpovídají í klauzulím proto, ¾e pøi ohodno ení má ka¾dá klauzule hodnotu true. 0
0
i
i
i
Pøevod 3-SAT na ILP
Tvrzení Jestli¾e existuje øe¹ení vytvoøené soustavy nerovni , pak je formule ' splnitelná.
Dùkaz: Je zøejmé, ¾e pokud má soustava nerovni øe¹ení, tak musí toto øe¹ení pro v¹e hna x splòovat podmínku x 2 f0; 1g. 0
0
i
i
Tomuto øe¹ení tedy jednoznaènì odpovídá nìjaké ohodno ení a z pøed hozího je zøejmé, ¾e ka¾dá klauzule formule ' pøi tomto ohodno ení nabývá hodnoty true, tak¾e platí ['℄ =
a formule ' je tedy splnitelná.
true
Pøevod 3-SAT na ILP
Vidíme, ¾e formule ' je splnitelná právì tehdy, kdy¾ existuje
eloèíselné øe¹ení k ní vytvoøené soustavy nerovni . Tím je dùkaz korektnosti konstruk e hotov.
