10-prevody/10-prevody.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{10}{Pøevody problémù}{(zapsali Martin Chytil, Vladimír Kudelas)}
   4
   5 \>Na této pøedná¹ce se budeme zabývat rozhodovacími problémy a jejich obtí¾ností.
   6 Za jednoduché budeme trochu zjednodu¹enì pova¾ovat ty problémy, na~nì¾ známe algoritmus
   7 pracující v~polynomiálním èase.
   8
   9 \s{Definice:} {\I Rozhodovací problém} je takový problém, jeho¾ výstupem je v¾dy {\sc ano}, nebo {\sc ne}.
  10 [Formálnì bychom se na~nìj mohli dívat jako na~mno¾inu $L$ vstupù, na~které je odpovìï {\sc ano},
  11 a místo $L(x)=\hbox{\sc ano}$ psát prostì $x\in L$.]
  12
  13 \s{Pøíklad:} Je dán bipartitní graf $G$ a $k \in {\bb N}$. Existuje v $G$ párování, které obsahuje alespoò $k$ hran?
  14
  15 To, co bychom ve~vìt¹inì pøípadù chtìli, je samozøejmì nejen zjistit, zda takové párování
  16 existuje, ale také nìjaké konkrétní najít. V¹imnìme si ale, ¾e kdy¾ umíme rozhodovat
  17 existenci párování v~polynomiálním èase, mù¾eme ho polynomiálnì rychle i najít:
  18
  19 Mìjme èernou skøíòku (fungující v polynomiálním èase), která odpoví, zda daný
  20 graf má nebo nemá párování o~$k$ hranách. Odebereme z~grafu libovolnou hranu
  21 a zeptáme se, jestli i tento nový graf má párovaní velikosti~$k$. Kdy¾ má, pak tato
  22 hrana nebyla pro existenci párování potøebná, a~tak ji odstraníme. Kdy¾ naopak
  23 nemá (hrana patøí do ka¾dého párování po¾adované velikosti), tak si danou hranu
  24 poznamenáme a odebereme nejen ji a její vrcholy, ale také hrany, které do tìchto
  25 vrcholù vedly. Toto je korektní krok, proto¾e v pùvodním grafu tyto vrcholy
  26 byly navzájem spárované, a tedy nemohou být spárované s~¾ádnými jinými vrcholy.
  27 Na~nový graf aplikujeme znovu tentý¾ postup. Výsledkem je mno¾ina hran, které patøí
  28 do hledaného párování. Hran, a tedy i iterací na¹eho algoritmu, je polynomiálnì
  29 mnoho a skøíòka funguje v polynomiálním èase, tak¾e celý algoritmus je polynomiální.
  30
  31 A~jak ná¹ rozhodovací problém øe¹it? Nejsnáze tak, ¾e ho pøevedeme na~jiný, který
  32 u¾ vyøe¹it umíme. Tento postup jsme (právì u~hledání párování) u¾ pou¾ili
  33 v~kapitole o~Dinicovì algoritmu. Vytvoøili jsme vhodnou sí», pro kterou
  34 platilo, ¾e v~ní existuje tok velikosti~$k$ právì tehdy, kdy¾
  35 v~pùvodním grafu existuje párování velikosti~$k$.
  36
  37 Takovéto pøevody mezi problémy mù¾eme definovat obecnì:
  38
  39 \s{Definice:} Jsou-li $A$, $B$ rozhodovací problémy, pak øíkáme, ¾e $A$ lze {\I
  40 redukovat} (neboli pøevést) na $B$ (pí¹eme $A \rightarrow B$) $\Leftrightarrow$
  41 existuje funkce $f$ spoèitatelná v polynomiálním èase taková, ¾e pro $\forall
  42 x: A(x) = B(f(x))$.
  43
  44 V¹imnìte si, ¾e $A\rightarrow B$ také znamená, ¾e problém~$B$ je alespoò tak tì¾ký
  45 jako problém~$A$ (tím myslíme, ¾e pokud lze $B$ øe¹it v~polynomiálním èase,
  46 lze tak øe¹it i~$A$): Nech» problém~$B$ umíme øe¹it v~èase $\O(b^k)$, kde
  47 $b$ je délka jeho vstupu. Nech» dále funkce $f$ pøevádìjící $A$ na $B$ pracuje
  48 v~èase $\O(a^\ell)$ pro vstup délky~$a$. Spustíme-li tedy $B(f(x))$ na~nìjaký
  49 vstup~$x$ problému~$A$, bude mít $f(x)$ délku $\O(a^\ell)$, tak¾e $B(f(x))$
  50 pobì¾í v~èase $\O(a^{k\ell})$, co¾ je polynomiální v~délce vstupu~$a$.
  51
  52
  53 \s{Pozorování:} Pøevoditelnost je:
  54 \itemize\ibull
  55 \:reflexivní (úlohu mù¾eme pøevést na tu stejnou identickým zobrazením): $A \rightarrow A$,
  56 \:tranzitivní: Je-li $A \rightarrow B$ funkcí $f$, $B \rightarrow C$ funkcí $g$, pak $A \rightarrow C$ slo¾enou funkcí $g \circ f$
  57 (slo¾ení dvou polynomiálních funkcí je zase polynomiální funkce, jak u¾ jsme zpozorovali
  58 v~pøedchozím odstavci).
  59 \endlist
  60
  61 \>Podívejme se nyní na~pøevody mezi dal¹ími zajímavými problémy:
  62
  63 \h{1. problém: SAT}
  64 \>Splnitelnost logických formulí, tj. dosazení \<true> èi \<false> za promìnné v logické formuli tak, aby formule dala výsledek \<true>.
  65
  66 \>Zamìøíme se na speciální formu zadání formulí,  {\I konjunktivní normální formu} (CNF).
  67 $$(\ldots\lor\ldots\lor\ldots\lor\ldots) \land (\ldots\lor\ldots\lor\ldots\lor\ldots) \land \ldots $$
  68
  69 \>{\I Vstup:} Formule $\varphi$ v konjunktivní normální formì.
  70
  71 \>{\I Výstup:} $\exists$ dosazení \<true> a \<false> za promìnné takové, ¾e hodnota formule $\varphi(\ldots) = \<true>$.
  72
  73 \>Pro formuli platí následující podmínky:
  74
  75 \itemize\ibull
  76 \:{\I formule} je zadána pomocí {\I klauzulí} oddìlených $\land$,
  77 \:ka¾dá {\I klauzule} je slo¾ená z {\I literálù} oddìlených $\lor$,
  78 \:ka¾dý {\I literál} je buïto promìnná nebo její negace.
  79 \endlist
  80
  81 \>Uká¾eme, ¾e staèí vyøe¹it jednodu¹¹í problém 3-SAT.
  82
  83 \h{2. problém: 3-SAT}
  84 \s{Definice:} 3-SAT je takový SAT, v nìm¾ ka¾dá klauzule obsahuje nejvý¹e tøi literály.
  85
  86 \s{Pøevod 3-SAT na SAT:}
  87 Vstup není potøeba nijak upravovat, 3-SAT splòuje vlastnosti SATu, proto 3-SAT $\rightarrow$ SAT (3-SAT je alespoò tak tì¾ký jako SAT)
  88
  89 \s {Pøevod SAT na 3-SAT:}
  90 Musíme formuli pøevést tak, abychom neporu¹ili splnitelnost.
  91
  92 \>Trik pro dlouhé klauzule: Ka¾dou klauzuli
  93 $$(\alpha \lor \beta) \hbox{, t¾. } \vert\alpha\vert + \vert\beta\vert \ge 4$$
  94 pøepí¹eme na: $$(\alpha \lor x) \land (\beta \lor \lnot x),$$
  95 kde $x$ je nová promìnná, kterou nastavíme tak, abychom neovlivnili splnitelnost formule.
  96
  97 \>Platí-li:
  98 \itemize\ibull
  99 \:$\alpha \Rightarrow x = 0$ (zajistí splnìní druhé poloviny nové formule),
 100 \:$\beta \Rightarrow x = 1$ (zajistí splnìní první poloviny nové formule),
 101 \:$\alpha ,\beta / \lnot\alpha ,\lnot\beta \Rightarrow x = 0/1$ (je nám to jedno, celkové øe¹ení nám to neovlivní).
 102 \endlist
 103
 104 \>Tento trik opakujeme tak dlouho, dokud je to tøeba.
 105
 106 Nabízí se otázka, proè mù¾eme promìnnou $x$ nastavit, jak se nám zlíbí. Vysvìtlení je prosté, promìnná $x$ nám pùvodní formuli nijak neovlivní, proto¾e se v ní nevyskytuje, proto ji mù¾eme nastavit tak, jak chceme.
 107
 108 \s{Poznámka:} U~3-SAT lze vynutit právì tøi literály, pro krátké klauzule pou¾ijeme následující trik:
 109 $$(\alpha) \rightarrow (\alpha \lor x) \land (\alpha \lor \lnot x).$$
 110
 111 \h{3. problém: Hledání nezávislé mno¾iny v grafu}
 112
 113 \>Existuje nezávislá mno¾ina vrcholù z~$G$ velikosti alespoò $k$?
 114
 115 \s{Definice:} {\I Nezávislá mno¾ina} (NzMna) budeme øíkat ka¾dé mno¾inì vrcholù grafu
 116 takové, ¾e mezi nimi nevede ¾ádná hrana.
 117
 118 \figure{nezmna.eps}{Pøíklad nezávislé mno¾iny}{1in}
 119
 120 \>{\I Vstup:} Neorientovaný graf G, $k \in {\bb N}$.
 121
 122 \>{\I Výstup:} $\exists A \subseteq V(G)$, $\vert A \vert \ge k$: $\forall u,v \in A \Rightarrow uv \not\in E(G)$?
 123
 124 \s{Poznámka:} Ka¾dý graf má minimálnì jednu nezávislou mno¾inu, a tou je prázdná mno¾ina. Proto je potøeba zadat i minimální velikost hledané mno¾iny.
 125
 126 \>Uká¾eme, jak na~tento probém pøevést 3-SAT.
 127
 128 \s{Pøevod:} Z ka¾dé klauzule vybereme jeden literál tak, abychom v rùzných klauzulích nevybírali konfliktnì, tj. $x$ a $\lnot x$.
 129
 130 \s{Pøíklad:}
 131 $(x \lor y \lor z) \land (x \lor \lnot y \lor \lnot z) \land (\lnot x \lor \lnot y \lor p) $.
 132
 133 \>Pro ka¾dou klauzuli sestrojíme graf (trojúhelník) a pøidáme \uv{konfliktní} hrany, tj. $x$ a $\lnot x$.
 134
 135 Princip je takový, ¾e z~ka¾dé klauzule si vybereme literál, který danou
 136 klauzuli splní, a to tak, aby literály, které si vybereme, nekolidovaly. Kolize
 137 o¹etøíme hranami mezi promìnnými a jejich negacemi.
 138
 139 \figure{nezmna_graf.eps}{Ukázka pøevodu 3-SAT na nezávislou mno¾inu}{3in}
 140
 141 Existuje nezávislá mno¾ina velikosti rovné poètu klauzulí?
 142 Pokud ano, tak dostaneme seznam promìnných, pomocí kterých splníme danou formuli.
 143
 144 \s{Pøevod NzMna na SAT:}
 145 Máme promìnné $v_1, \ldots , v_n$ pro vrcholy.
 146
 147 \>Nyní uká¾eme, jak pøevést problém hledání nezávislé mno¾iny, na SAT.
 148
 149 \itemize\ibull
 150 \:Poøídíme si promìnné $v_1, \ldots, v_n$ odpovídající vrcholùm grafu. Promìnná $v_i$ bude
 151   indikovat, zda se $i$-tý vrchol vyskytuje v~nezávislé mno¾inì.
 152 \:Pro ka¾dou hranu $ij \in E(G)$ pøidáme klauzuli $(\lnot v_i \lor \lnot v_j)$. Tyto klauzule
 153   nám ohlídají, ¾e vybraná mno¾ina je vskutku nezávislá.
 154 \:Je¹tì potøebujeme zkontrolovat, ¾e je mno¾ina dostateènì velká, tak¾e si její prvky
 155   oèíslujeme èísly od~1 do~$k$. Oèíslování popí¹eme maticí promìnných $x_{ij}$, pøièem¾
 156   $x_{ij}$ bude pravdivá právì tehdy, kdy¾ v~poøadí $i$-tý prvek nezávislé mno¾iny je vrchol~$v_j$.
 157 \:Pøidáme tedy klauzuje, které nám øeknou, ¾e vybrané do nezávislé mno¾iny jsou právì
 158   ty vrcholy, které jsou touto maticí oèíslované: $\forall i,j$, $x_{ij} \Rightarrow v_j$.
 159 \:Je¹tì potøebujeme zajistit, aby byla v~ka¾dém øádku i sloupci nejvý¹e jedna jednièka:
 160   $\forall j,i,i^{'}, i\ne i^{'} : x_{ij} \Rightarrow \lnot x_{i^{'}j}$ a
 161   $\forall i,j,j^{'}, j\ne j^{'} : x_{ij} \Rightarrow \lnot x_{ij^{'}}$.
 162 \:A~nakonec si ohlídáme, aby v~ka¾dém øádku byla alespoò jedna jednièka, klauzulí $\forall i :
 163   x_{i1} \lor x_{i2} \lor \ldots \lor x_{in}$.
 164 \endlist
 165
 166 \figure{matice.eps}{Výsledná matice}{3in}
 167
 168 \h{4. problém: Klika}
 169
 170 \>{\I Vstup:} Graf $G, k \in N$.
 171
 172 \>{\I Výstup:} $\exists$ úplný podgraf grafu $G$ na $k$ vrcholech?
 173 \figure{klika.eps}{Pøíklad kliky}{3in}
 174
 175 \s{Pøevod:} Prohodíme v grafu $G$ hrany a nehrany $\Rightarrow$ hledání nezávislé mno¾iny.
 176
 177 \s{Dùvod:} Pokud existuje úplný graf na $k$ vrcholech, tak v~\uv{invertovaném} grafu tyto vrcholy nejsou spojeny hranou, tj. tvoøí nezávislou mno¾inu.
 178
 179 \figure{doplnek_nm.eps}{Prohození hran a nehran}{3in}
 180
 181 \h{5. problém: 3D párování (3D matching)}
 182
 183 \>{\I Vstup:} Tøi mno¾iny, napø. $K$ (kluci), $H$ (holky), $Z$ (zvíøátka) a mno¾ina kompatibilních trojic (tìch, kteøí se spolu snesou).
 184
 185 \>{\I Výstup:} Perfektní podmno¾ina trojic - tj. taková podmno¾ina trojic, která obsahuje v¹echna $K$, $H$ a $Z$.
 186
 187 \>Uká¾eme, jak tento problém pøevést na 3,3-SAT (ov¹em to a¾ na dal¹í pøedná¹ce).
 188
 189 \figure{3d_parovani.eps}{Ukázka 3D párování}{3in}
 190
 191
 192 \h{6. problém: 3,3-SAT}
 193 \s{Definice:} 3,3-SAT je speciální pøípad 3-SATu, kde ka¾dá promìnná se vyskytuje v~maximálnì tøech literálech.
 194
 195 \s{Pøevod 3-SAT na 3,3-SAT:}
 196 Pokud se promìnná $x$ vyskytuje v~$k > 3$ literálech, tak nahradíme výskyty novými promìnnými $x_1, \ldots , x_k$ a pøidáme klauzule:
 197 $$
 198 (\lnot x_1 \lor x_2)
 199 (\lnot x_2 \lor x_3)
 200 (\lnot x_3 \lor x_4)
 201 \ldots
 202 (\lnot x_{k-1} \lor x_k)
 203 (\lnot x_k \lor x_1),
 204 $$
 205
 206 co¾ odpovídá:
 207
 208 $$
 209 (x_1 \Rightarrow x_2)
 210 (x_2 \Rightarrow x_3)
 211 (x_3 \Rightarrow x_4)
 212 \ldots
 213 (x_{k-1} \Rightarrow x_k)
 214 (x_k \Rightarrow x_1).
 215 $$
 216
 217 Tímto zaruèíme, ¾e v¹echny promìnné budou mít stejnou hodnotu. Navíc si lze v¹imnout, ¾e ka¾dý literál se vyskytuje nejvíce dvakrát.
 218
 219 \s{Závìr:} Obrázek ukazuje problémy, jimi¾ jsme se dnes zabývali, a vztahy mezi tìmito problémy.
 220 \figure{prevody.eps}{Pøevody mezi problémy}{3in}
 221
 222 \bye