10-prevody/10-prevody.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{10}{Pøevody problémù}{\vbox{\hbox{(zapsali Martin Chytil, Vladimír Kudelas,}\hbox{ Michal Kozák, Vojta Tùma)}}}
   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 Vstupy mìjme zakódované jen pomocí nul a jednièek (obecnì je jedno, jaký základ pro soustavu
  14 kódování zvolíme, pøevody mezi poyladickými soustavami jsou co do velikosti polynomiální). Rozhodovací problém
  15 zadefinujeme jako $f:\ \{0,1\}^{\ast} \to \{0,1\}$, to jest funkci z mno¾iny v¹ech øetìzcù jednièek a nul
  16 do mno¾iny $\{1,0\}$, kde 1 na výstupu znamená {\sc ano}, 0 {\sc ne}.
  17
  18 \s{Pøíklad:} Je dán bipartitní graf $G$ a $k \in {\bb N}$. Existuje v $G$
  19 párování, které obsahuje alespoò $k$ hran?
  20
  21 To, co bychom ve~vìt¹inì pøípadù chtìli, je samozøejmì nejen zjistit, zda takové párování
  22 existuje, ale také nìjaké konkrétní najít. V¹imnìme si ale, ¾e kdy¾ umíme rozhodovat
  23 existenci párování v~polynomiálním èase, mù¾eme ho polynomiálnì rychle i najít:
  24
  25 Mìjme èernou skøíòku (fungující v polynomiálním èase), která odpoví, zda daný
  26 graf má nebo nemá párování o~$k$ hranách. Odebereme z~grafu libovolnou hranu
  27 a zeptáme se, jestli i tento nový graf má párovaní velikosti~$k$. Kdy¾ má, pak tato
  28 hrana nebyla pro existenci párování potøebná, a~tak ji odstraníme. Kdy¾ naopak
  29 nemá (hrana patøí do ka¾dého párování po¾adované velikosti), tak si danou hranu
  30 poznamenáme a odebereme nejen ji a její vrcholy, ale také hrany, které do tìchto
  31 vrcholù vedly. Toto je korektní krok, proto¾e v pùvodním grafu tyto vrcholy
  32 byly navzájem spárované, a tedy nemohou být spárované s~¾ádnými jinými vrcholy.
  33 Na~nový graf aplikujeme znovu tentý¾ postup. Výsledkem je mno¾ina hran, které patøí
  34 do hledaného párování. Hran, a tedy i iterací na¹eho algoritmu, je polynomiálnì
  35 mnoho a skøíòka funguje v polynomiálním èase, tak¾e celý algoritmus je polynomiální.
  36
  37 A~jak ná¹ rozhodovací problém øe¹it? Nejsnáze tak, ¾e ho pøevedeme
  38 na~{jiný\footnote{${}^{\dag}$}{vìrni matfyzáckým vtipùm}}, který
  39 u¾ vyøe¹it umíme. Tento postup jsme (právì u~hledání párování) u¾ pou¾ili
  40 v~kapitole o~Dinicovì algoritmu. Vytvoøili jsme vhodnou sí», pro kterou
  41 platilo, ¾e v~ní existuje tok velikosti~$k$ právì tehdy, kdy¾
  42 v~pùvodním grafu existuje párování velikosti~$k$.
  43
  44 Takovéto pøevody mezi problémy mù¾eme definovat obecnì:
  45
  46 \s{Definice:} Jsou-li $A$, $B$ rozhodovací problémy, pak øíkáme, ¾e $A$ lze {\I
  47 redukovat} (neboli pøevést) na $B$ (pí¹eme $A \rightarrow B$) $\equiv$
  48 existuje funkce $f$ spoèitatelná v polynomiálním èase taková, ¾e pro $\forall
  49 x: A(x) = B(f(x))$. V¹imnìme si, ¾e $f$ pracující v polynomiálním èase vstup
  50 zvìt¹í nejvíce polynomiálnì.
  51
  52 \s{Pozorování:} $A\rightarrow B$ také znamená, ¾e problém~$B$ je alespoò tak tì¾ký
  53 jako problém~$A$ (tím myslíme, ¾e pokud lze $B$ øe¹it v~polynomiálním èase,
  54 lze tak øe¹it i~$A$): Nech» problém~$B$ umíme øe¹it v~èase $\O(b^k)$, kde
  55 $b$ je délka jeho vstupu. Nech» dále funkce $f$ pøevádìjící $A$ na $B$ pracuje
  56 v~èase $\O(a^\ell)$ pro vstup délky~$a$. Spustíme-li tedy $B(f(x))$ na~nìjaký
  57 vstup~$x$ problému~$A$, bude mít $f(x)$ délku $\O(a^\ell)$, tak¾e $B(f(x))$
  58 pobì¾í v~èase $\O(a^\ell + (a^\ell)^k) = \O(a^{k\ell})$, co¾ je polynomiální
  59 v~délce vstupu~$a$.
  60
  61
  62 \s{Pozorování:} Pøevoditelnost je
  63 \itemize\ibull
  64 \:reflexivní (úlohu mù¾eme pøevést na tu stejnou identickým zobrazením): $A \rightarrow A$,
  65 \:tranzitivní: Je-li $A \rightarrow B$ funkcí $f$, $B \rightarrow C$ funkcí $g$,
  66 pak $A \rightarrow C$ slo¾enou funkcí $g \circ f$
  67 (slo¾ení dvou polynomiálních funkcí je zase polynomiální funkce, jak u¾ jsme zpozorovali
  68 v~pøedchozím odstavci).
  69 \endlist
  70 \>Takovýmto relacím øíkáme kvaziuspoøádání -- nesplòují obecnì antisymetrii, tedy mù¾e nastat
  71 $A\rightarrow B$ a $B\rightarrow A$. Omezíme-li se v¹ak na tøídy navzájem pøevoditelných
  72 problémù, dostáváme ji¾ (èásteèné) uspoøádání. Existují i navzájem nepøevoditelné problémy --
  73 napøíklad problém v¾dy odpovídající 1 a problém v¾dy odpovídající 0.
  74 Podívejme se nyní na~pøevody mezi dal¹ími zajímavými problémy:
  75
  76 \h{1. problém: SAT}
  77 \>Splnitelnost (satisfiability) logických formulí, tj. dosazení 1 èi
  78 0 za promìnné v logické formuli tak, aby formule dala výsledek 1.
  79
  80 \>Zamìøíme se na speciální formu zadání formulí,  {\I konjunktivní normální formu} (CNF),
  81         které splòují následující podmínky:
  82 \itemize\ibull
  83 \:{\I formule} je zadána pomocí {\I klauzulí}\footnote{${}^{\dag}$}{bez politických konotací} oddìlených $\land$,
  84 \:ka¾dá {\I klauzule} je slo¾ená z {\I literálù} oddìlených $\lor$,
  85 \:ka¾dý {\I literál} je buïto promìnná nebo její negace.
  86 \endlist
  87 formule mají tedy tvar:
  88 $$\psi = (\ldots\lor\ldots\lor\ldots\lor\ldots) \land (\ldots\lor\ldots\lor\ldots\lor\ldots) \land \ldots $$
  89
  90 \>{\I Vstup:} Formule $\psi$ v konjunktivní normální formì.
  91
  92 \>{\I Výstup:} $\exists$ dosazení 1 a 0 za promìnné takové, ¾e hodnota formule $\psi(\ldots) = 1$.
  93
  94
  95
  96 \>Pøevod nìjaké obecné formule $\psi$ na jí ekvivalentní $\chi$ v CNF mù¾e
  97 zpùsobit, ¾e $\chi$ je exponenciálnì velká vùèi $\psi$.
  98 Lze ov¹em podniknout pøevod na takovou formuli $\chi'$ v CNF, která sice není
  99 ekvivalentní s $\psi$ (tedy ne ka¾dý model
 100 $\psi$ je modelem $\chi'$), ale je splnitelná právì tehdy, kdy¾ je splnitelná $\psi$ --- co¾ nám
 101 pøesnì staèí --- a je lineárnì velká vùèi $\psi$.
 102
 103 \h{2. problém: 3-SAT}
 104 \s{Definice:} 3-SAT je takový SAT, v nìm¾ ka¾dá klauzule obsahuje nejvý¹e tøi literály.
 105
 106 \s{Pøevod 3-SAT na SAT:}
 107 Vstup není potøeba nijak upravovat, 3-SAT splòuje vlastnosti SATu, proto 3-SAT
 108 $\rightarrow$ SAT (SAT je alespoò tak tì¾ký jako 3-SAT)
 109
 110 \s {Pøevod SAT na 3-SAT:}
 111 Musíme formuli pøevést tak, abychom neporu¹ili splnitelnost.
 112
 113 \>Trik pro dlouhé klauzule: Ka¾dou \uv{¹patnou} klauzuli
 114 $$(\alpha \lor \beta) \hbox{, t¾. } \vert\alpha\vert + \vert\beta\vert \ge 4
 115 ,\ \vert\alpha\vert \geq 2,\ \vert\beta\vert\geq 2$$
 116 pøepí¹eme na: $$(\alpha \lor x) \land (\beta \lor \lnot x),$$
 117 kde $x$ je nová promìnná, kterou nastavíme tak, abychom neovlivnili splnitelnost formule.
 118
 119 \>Platí-li:
 120 \itemize\ibull
 121 \:$\alpha \Rightarrow x = 0$ (zajistí splnìní druhé poloviny nové formule),
 122 \:$\beta \Rightarrow x = 1$ (zajistí splnìní první poloviny nové formule),
 123 \:$\alpha ,\beta / \lnot\alpha ,\lnot\beta \Rightarrow x = 0/1$ (je nám to jedno, celkové øe¹ení nám to neovlivní).
 124 \endlist
 125
 126 \>Tento trik opakujeme tak dlouho, dokud je to tøeba -- formuli délky $k+l$
 127 roztrhneme na formule délky $k+1$ a $l+1$. Pokud klauzule pùlíme, dostaneme
 128 polynomiální èas (strom rekurze má logaritmicky pater -- formule délky alespoò 6
 129 se nám pøi rozdìlení zmen¹í na dvì instance velikosti maximálnì $2/3$ pùvodní, krat¹í
 130 formule nás netrápí; na ka¾dém patøe se vykoná tolik co na pøedchozím + $2^{hloubka}$
 131 za pøidané formule). Velikost výsledné formule je polynomiální vùèi pùvodní:
 132 ¾ádný literál (výskyt promìnné) pùvodní klauzule neduplikujeme, a v nejhor¹ím
 133 pøípadì zùstane ka¾dý pùvodní literál v klauzuli sám s nìjakými dvìma pøidanými
 134 (klauzule o tøech pøidaných mù¾eme vypustit) -- tedy poèet literálu se
 135 maximálnì ztrojnásobí.
 136
 137 Nabízí se otázka, proè mù¾eme pøidanou promìnnou $x$ nastavovat, jak se nám zlíbí.
 138 Vysvìtlení je prosté -- promìnná $x$ nám pùvodní formuli nijak neovlivní, proto¾e
 139 se v ní nevyskytuje, proto ji mù¾eme nastavit tak, jak chceme.
 140
 141 \s{Poznámka:} U~3-SAT lze vynutit právì tøi literály, pro krátké klauzule
 142 pou¾ijeme stejný trik:
 143 $$(\alpha) \rightarrow (\alpha \vee \alpha) \rightarrow (\alpha \lor x) \land (\alpha \lor \lnot x).$$
 144
 145 \h{3. problém: Hledání nezávislé mno¾iny v grafu}
 146
 147 \>Existuje nezávislá mno¾ina vrcholù z~$G$ velikosti alespoò $k$?
 148
 149 \s{Definice:} {\I Nezávislá mno¾ina} (NzMna) budeme øíkat ka¾dé mno¾inì vrcholù grafu
 150 takové, ¾e mezi nimi nevede ¾ádná hrana.
 151
 152 \figure{nezmna.eps}{Pøíklad nezávislé mno¾iny}{1in}
 153
 154 \>{\I Vstup:} Neorientovaný graf G, $k \in {\bb N}$.
 155
 156 \>{\I Výstup:} $\exists A \subseteq V(G)$, $\vert A \vert \ge k$: $\forall u,v \in A \Rightarrow uv \not\in E(G)$?
 157
 158 \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.
 159
 160 \>Uká¾eme, jak na~tento probém pøevést 3-SAT.
 161
 162 \s{Pøevod 3-SAT na NzMna:} Z ka¾dé klauzule vybereme jeden literál tak, abychom v rùzných klauzulích nevybírali konfliktnì, tj. $x$ a $\lnot x$.
 163
 164 \s{Pøíklad:}
 165 $(x \lor y \lor z) \land (x \lor \lnot y \lor \lnot z) \land (\lnot x \lor \lnot y \lor p) $.
 166
 167 \>Pro ka¾dou klauzuli sestrojíme graf (trojúhelník) a pøidáme \uv{konfliktní}
 168 hrany, tj. $x$ a $\lnot x$. Poèet vrcholù grafu odpovídá poètu literálù ve formuli,
 169 poèet hran je maximálnì kvadratický a pøevod je tedy polynomiální.
 170
 171 Existuje-li v grafu nezávislá mno¾ina velikosti $k$, pak z právì $k$ trojúhelníkù
 172 vybere právì jeden vrchol, a pøitom ¾ádné dva vrcholy nebudou odpovídat literálu a
 173 jeho negaci -- tedy dostaneme ohodnocení promìnných splòujících alespoò $k$ klauzulí.
 174 Na druhou stranu, existuje-li ohodnocení $k$ klauzulí, pak pøímo odpovídá nezávislé
 175 mno¾inì velikosti $k$. Ptáme-li se tedy na nezávislou mno¾inu velikosti odpovídající
 176 poètu klauzulí, dostaneme odpovìï {\sc ano} právì tehdy, kdy¾ je formule splnitelná.
 177
 178 Jsou-li ve formuli i klauzule krat¹í ne¾ 3, mù¾eme je buïto prodlou¾it metodou vý¹e
 179 popsanou; nebo si v grafu necháme dvoj- a jedno-úhelníky, které ¾ádné z na¹ich úvah
 180 vadit nebudou.
 181
 182 \figure{nezmna_graf.eps}{Ukázka pøevodu 3-SAT na nezávislou mno¾inu}{3in}
 183
 184 \s{Pøevod NzMna na SAT:}
 185 Máme promìnné $v_1, \ldots , v_n$ pro vrcholy.
 186
 187 \>Nyní uká¾eme, jak pøevést problém hledání nezávislé mno¾iny, na SAT.
 188
 189 \itemize\ibull
 190 \:Poøídíme si promìnné $v_1, \ldots, v_n$ odpovídající vrcholùm grafu. Promìnná $v_i$ bude
 191   indikovat, zda se $i$-tý vrchol vyskytuje v~nezávislé mno¾inì (tedy pøíslu¹né ohodnocení
 192   promìnných bude vlastnì charakteristická funkce nezávislé mno¾iny).
 193 \:Pro ka¾dou hranu $ij \in E(G)$ pøidáme klauzuli $(\lnot v_i \lor \lnot v_j)$. Tyto klauzule
 194   nám ohlídají, ¾e vybraná mno¾ina je vskutku nezávislá..
 195 \:Je¹tì potøebujeme zkontrolovat, ¾e je mno¾ina dostateènì velká, tak¾e si její prvky
 196   oèíslujeme èísly od~1 do~$k$. Oèíslování popí¹eme maticí promìnných $x_{ij}$, pøièem¾
 197   $x_{ij}$ bude pravdivá právì tehdy, kdy¾ v~poøadí $i$-tý prvek nezávislé mno¾iny je vrchol~$v_j$
 198 -- pøidáme tedy klauzule, které nám øeknou, ¾e vybrané do nezávislé mno¾iny jsou právì
 199   ty vrcholy, které jsou touto maticí oèíslované: $\forall i,j$, $x_{ij} \Rightarrow v_j$
 200   (jen dodejme, ¾e $a\Rightarrow b$ je definované jako $\neg a\vee b$).
 201 \:Je¹tì potøebujeme zajistit, aby byla v~ka¾dém øádku i sloupci nejvý¹e jedna jednièka:
 202   $\forall j,i,i^{'}, i\ne i^{'} : x_{ij} \Rightarrow \lnot x_{i^{'}j}$ a
 203   $\forall i,j,j^{'}, j\ne j^{'} : x_{ij} \Rightarrow \lnot x_{ij^{'}}$..
 204 \:A~nakonec si ohlídáme, aby v~ka¾dém øádku byla alespoò jedna jednièka, klauzulí $\forall i :
 205   x_{i1} \lor x_{i2} \lor \ldots \lor x_{in}$.
 206 \endlist
 207 Takovýto pøevod je zøejmì polynomiální.
 208
 209 \s{Pøíklad matice:} Jako pøíklad pou¾ijeme nezávislou mno¾inu z ukázky nezávislé mno¾iny.
 210 Nech» jsou vrcholy grafu oèíslované zleva a ze zhora. Hledáme nezávislou mno¾inu velikosti $2$.
 211 Matice pak bude vypadat následovnì:
 212 $$ \pmatrix{1&0&0&0&0 \cr 0&0&0&1&0}$$
 213 \s{Vysvìtlení:} Jako první vrchol mno¾iny bude vybrán vrchol $v_1$, proto v prvním
 214 øádku a v prvním sloupci bude $1$. Jako druhý ($k$-tý) vrchol mno¾iny bude vybrán
 215 vrchol $v_4$, proto na druhém ($k$-tém) øádku a ve ètvrtém sloupci bude $1$. Na ostatních místech bude $0$.
 216
 217 \h{4. problém: Klika}
 218
 219 \>{\I Vstup:} Graf $G, k \in N$.
 220
 221 \>{\I Výstup:} $\exists$ úplný podgraf grafu $G$ na $k$ vrcholech?
 222 \figure{klika.eps}{Pøíklad kliky}{2in}
 223
 224 \s{Pøevod:} Prohodíme v grafu $G$ hrany a nehrany $\Rightarrow$ (hledání nezávislé mno¾iny $\leftrightarrow$ hledání kliky).
 225
 226 \s{Dùvod:} Pokud existuje úplný graf na $k$ vrcholech, tak v~komplementárním grafu tyto vrcholy nejsou spojeny hranou, tj. tvoøí nezávislou mno¾inu,
 227         a naopak.
 228
 229 \figure{doplnek_nm.eps}{Prohození hran a nehran}{2in}
 230
 231
 232 \h{5. problém: 3,3-SAT}
 233 \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.
 234
 235 \s{Pøevod 3-SAT na 3,3-SAT:}
 236 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:
 237 $$
 238 (\lnot x_1 \lor x_2),
 239 (\lnot x_2 \lor x_3),
 240 (\lnot x_3 \lor x_4),
 241 \ldots,
 242 (\lnot x_{k-1} \lor x_k),
 243 (\lnot x_k \lor x_1),
 244 $$
 245
 246 co¾ odpovídá:
 247
 248 $$
 249 (x_1 \Rightarrow x_2),
 250 (x_2 \Rightarrow x_3),
 251 (x_3 \Rightarrow x_4),
 252 \ldots,
 253 (x_{k-1} \Rightarrow x_k),
 254 (x_k \Rightarrow x_1).
 255 $$
 256
 257 Tímto zaruèíme, ¾e v¹echny nové promìnné budou mít stejnou hodnotu.
 258
 259 Mimochodem, mù¾eme rovnou zaøídit, ¾e ka¾dý literál se vyskytuje nejvíce dvakrát (tedy ¾e
 260 ka¾dá promìnná se vyskytuje alespoò jednou pozitivnì a alespoò jednou negativnì). Pokud by
 261 se nìjaká promìnná objevila ve~tøech stejných literálech, mù¾eme na~ni
 262 také pou¾ít ná¹ trik a nahradit ji tøemi promìnnými. V~nových klauzulích se pak bude
 263 vyskytovat jak pozitivnì, tak negativnì.
 264
 265 \h{6. problém: 3D párování (3D matching)}
 266
 267 \>{\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).
 268
 269 \>{\I Výstup:} Perfektní podmno¾ina trojic - tj. taková podmno¾ina trojic, která obsahuje v¹echna $K$, $H$ a $Z$.
 270
 271 \>Uká¾eme, jak tento problém pøevést na 3,3-SAT (ov¹em to a¾ na dal¹í pøedná¹ce).
 272
 273 \figure{3d_parovani.eps}{Ukázka 3D párování}{3in}
 274
 275 \s{Závìr:} Obrázek ukazuje problémy, jimi¾ jsme se dnes zabývali, a vztahy mezi tìmito problémy.
 276 \figure{prevody.eps}{Pøevody mezi problémy}{3in}
 277
 278 \bye