IB107 Vyčíslitelnost a složitost
polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER
Jan Strejček
Fakulta informatiky Masarykova univerzita
polynomiální redukce
Definice (polynomiální redukce)
Necht A c Z* a B c <t>* /sol/ jazyky. Řekneme, že A se polynomiálně redukuje na B, píšeme A <p B, právě když existuje totální funkce f: Z* -> <t>*, která je vyčíslitelná deterministickým Turingovým strojem pracujícím v polynomiálním čase a taková, že
w g A <=^> f(w) g B.
Funkci f nazveme polynomiální redukcí A na B.
Platí A <p B        A <p B.
Platí A<p B a B <p C        /A <p C (tj. <p je tranzitivní).
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER 2/24
polynomiální redukce a složitostní třídy
Věta
Necht A <p B. m B e P ^ Ae P m Be N P       A e N P
Důkaz: Nechí f je redukce A na B v polynomiálním čase a M b je TM rozhodující B. Stroj Ma rozhodující A na vstupu w
spočítá f(w)
spustí M b na vstupu f(w) a vrátí stejný výsledek jako M b
Je-li Mb deterministický, pak je i Ma deterministický. Krok 1 lze provést v polynomiálním čase vzhledem k \ w\, krok 2 v polynomiálním čase vzhledem k \f(w)\, což je polynomiální i vzhledem k \ w\. Ma tedy pracuje v polynomiálním čase.
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER
polynomiální redukce a složitostní třídy
Definice (těžká a úplná množina ve složitostní třídě)
NechtC je složitostní třída splňující N P c C. Jazyk L nazveme C-těžký, právě když pro každý jazyk U e C platí U <p L. Je-li navíc L e C, pak L nazýváme C-úplný nebo úplný ve třídě C.
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER
4/24
SAT je NP-úplný
Věta (Cookova-Levinova věta)
SAT = {(cp) | cp je splnitelná výroková formule} je NP-úplný.
Důkaz: SAT e NP jsme již dokázali.
Ukážeme, že SAT je NP-těžký, tj. A e NP       A <p SAT.
Nechí M je nedeterministický TM rozhodující A v čase p(n), kde p je polynom. Pro každé slovo w sestrojíme výrokovou formuli O, která je splnitelná, právě když stroj M má akceptující výpočet na w.
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER
5/24
SAT je NP-úplný
Každý výpočet stroje M pracujícího v čase p(ri) na slově w délky n lze reprezentovat tabulkou:
Vytvoříme 0, aby platilo:
0 je splnitelné <=^> existuje tabulka reprezentující
akceptující výpočet na w
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER 6/24
SAT je NP-úplný
0   = 0
cell
A 0
start
A 0
move
A 0
accept
0ceN = "každé XjjjS platí <=^> v tabulce na pozici /,/je symbol s, kde seC = Quru{#}"
*cell=       A       [( VX'V>*) A ( /\ ^(%A%))
1 </<p(n)+1 1 <y<p(n)+3
s,řeC
0ce„|GO(p2(a7))
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER
7/24
SAT je NP-úplný
4> = <Dcen A 0start A <t>
move A ^accept
0start = "na prvním řádku je iniciální konfigurace pro w =    ... wn"
^start   = A X1?2,Qo A Xi,3,> A
^1,4,^ A *i,5,w2 A ... A X-|?n+3?M/n A
*1,n+4,u A Xi,n+5,u A ... A X1?p(n)+2?u A X1?p(n)+3?#
^startl e C?(p(n))
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER
8/24
SAT je NP-úplný
<t> = Ocel, A Ostart A 4>
m o ve A ^accept
^move = "každé dva po sobě jdoucí řádky odpovídají kroku výpočtu" popíšeme pomocí "legálních oken" 2x3
příklady legálních oken pro S(q^, b) = {((fe, c, L), (g2ja, /?)}:
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER
9/24
SAT je NP-úplný
* = <t>cell A <t>start A <t>
move A ^accept
^move = "každé okno 2 x 3 v tabulce je legální" (okna se překrývají)
0
move
A
1 </<p(n)+1 1 <y<p(n)+3
v
legální okno
i—i—i—i
x/,y-l,ai A xiJ,a2 A x/',y+l,a3 A x/+1,y—1,a4 A x/+1,y,a5 A x/+1,y+1,a6
ai	a2	a3
a4	a5	a6
^moveI e 0(p2{n))
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER
10/24
SAT je NP-úplný
4> = <Dcen A 0start A <t>
move A "^accept
^accept = "v tabulce je stav qacc"
4>
accept
V
l,J,Qacc
1 </<p(n)+1 1 <y<p(n)+3
^acceptl e 0{p2{n))
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER
11/24
SAT je NP-úplný
<J> = <t>ceii a 0start a <t>
move a 0accept
<D| = 0{p2{n)) + 0{p{n)) + 0{p2{n)) + 0{p2{n)) = 0{p2{n))
Počet proměnných x/J?s závisí je 0(p2(n)), tedy závisí na n = \ w Proměnnou lze zakódovat do binární abecedy 0(\ogn) znaky. Tedy |(ct>)| = 0(p2(n) • logn), což znamená |(<t>}| = 0(p2(n) • n).
0} má polynomiální délku vzhledem k n = \ w\ a lze spočítat v polynomiálním čase. Tedy A <p SAT.
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER
12/24
konjunktivní normální forma (cnf) výrokových formulí
literal = je proměnná nebo její negace
klauzule = disjunkce literálů
formule v cnf = konjunkce klauzulí
formule v 3cnf = formule v cnf, kde každá klauzule má 3 literály
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER 13/24
problém 3SAT
Problém 3SAT je problém rozhodnout, zda je daná výroková formule v 3cnf splnitelná.
3SAT = {((p) \<p je splnitelná formule v 3cnf}
Věta
3 SAT je NP-úplný. Důkaz: 3SAT e NP:
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER 14/24
3SATje NP-úplný
3SAT je NP-těžký, tj. A e NP       A <p 3SAT: Q zkonstruujeme 0 jako v důkazu NP-těžkosti SATu
0 převedeme na ekvivalentní <t>; v cnf pomocí ekvivalence
(<p A ip) v p = (<p v p) A (ip v p)
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER
15/24
3SAT\e NP-úplný
<t>' převedeme na <t>" v 3cnf pomocí vztahů
h v/2 /1 v l2 v /3 /i v/2V/3V/4
/! v ^ v ... v /,
<í>" je splnitelná <^> <t>' je splnitelná <^> <t> je splnitelná
|<D"| g 0(p2(a7)). Tedy /\ <p 3S/\7. ■
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER 16/24
redukce a C-těžkost
NechtC je složitostní třída splňující NP c C.
A je C-těžký a A<PB =^ B je C-těžký
Důkaz:
Důsledek
Je-li A NP-úplný, A <p B a B e NP, pak B je také NP-úplný.
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER
problém CLIQUE
Definice (/c-klika)
Neorientovaný graf G má k-kliku, pokud v něm existuje úplný podgraf s k vrcholy.
Definice (problém CLIQUE)
Problém CLIQUE je problém rozhodnout, zda daný graf G má k-kliku pro dané k.
CLIQUE = {(G,k)\Gje graf s k-klikou}
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER
18/24
CLIQUE je NP-úplný
Věta
CLIQUE je NP-úplný. Důkaz: CLIQUE e NP:
CLIQUE je NP-těžký: 3SAT <p CLIQUE
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER
19/24
CLIQUE je NP-úplný
Nechí (p = fa v fy v d) a (a2 v ď2 v c2) a ... a (a/< v ^ v c*). Zkonstruujeme graf G = (\/, E), kde
■ l/ = {a1,Ď1,c1, a2, b2, c2,..., akl bkl ck} a
■ E =      , v2} | v-i, v2 nejsou ze stejné klauzule a
v-i není negací v2 nebo naopak}.
(p = (x v y v z) a (-.x v^yv -.z) a (x v -.y v ^y)
je splnitelná ^=^> existuje splňující prirazení Gmá/c-kliku Zároveň |G| = e>(M2) a tedy 3SAT <p CLIQUE. ■
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER 20/24
další NP-úplné problémy
■ problém hamiltonovské cesty HAMPATH
■ problém obchodního cestujícího
(rozhodovací problém: existuje cesta do dané velikosti?)
■ problém okáchličkování (tiling problém)
Eternity II
■ 256 dílků (16x16)
■ 2.000.000 dolarů za řešení
■ během 3 a půl roku nenalezeno
Lemma
Pokud je nějaký NP-úplný problém v P, pak P = N P.
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER
21/24
problém VERTEX-COVER
Definice (vrcholové pokrytí)
Necht G je neorientovaný graf. Podmnožina jeho vrcholů se nazývá vrcholové pokrytí grafu G, pokud obsahuje alespoň jeden vrchol každé hrany grafu G.
Definice (problém VERTEX-COVER)
Problém VERTEX-COVER je problém rozhodnout, zda daný graf G má vrcholové pokrytí obsahující právě daný počet vrcholů k.
VERTEX-COVER = {(G, k) \ G je graf s vrcholovým pokrytím
obsahujícím právě k vrcholů }
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER
22/24
VERTEX-COVER je NP-úplný
Věta
VERTEX-COVER je NP-úplný. Důkaz: VERTEX-COVER e NP:
VERTEX-COVER je NP-těžký: 3SAT <p VERTEX-COVER
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER
23/24
VERTEX-COVER je NP-ůplný
Nechí cp = fa v jfy v d) a (a2 v ď2 v c2) a ... a (a/ vů/v q) používá množinu proměnných X. Zkonstruujeme graf G = (V, E), kde
■ V = {a-i, Ď-i, Ci, a2, Ď2, c2,..., a/, £>/, c/} u {x, -.x \ x e X} a
■ E ={{a/5 Ď/}, {ah c,-}, {ď/, c,} | 1 < / < /} u {{x, -x} | x g X} u
u "hrany mezi literálem a shodným vrcholem x nebo -ix"
<p = (x v y v z) a (-.x v^yv -nz) a (x v -.y v -.y)
c^> je splnitelná <=^> G má vrcholové pokrytí s k = 21 + \X\ vrcholy Zároveň \G\ = 0(\<p\) a tedy 3SAT <p VERTEX-COVER. ■
IB107 Vyčíslitelnost a složitost: polynomiální redukce, SAT, 3SAT, CLIQUE, VERTEX-COVER 24/24