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 pøevody mezi nimi.
   6
   7 \s{Definice:} {\I Rozhodovací problém} je takový problém, jeho¾ výstupem je v¾dy {\sc ano}, nebo {\sc ne}.
   8
   9 \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?
  10
  11 \s{Pøíklad:} Daný problém pøevedeme na jiný: Párování $\rightarrow$ hledání maximálního toku (¹ipka znamená \uv{lze pøevést}).
  12 Tzn. existuje v nìjaké síti $G'$ tok velikosti alespoò $k$?
  13
  14 \s{Obecnì se dá øici:} Pokud daný pro rozhodovací problém umíme rozhodnout, zda platí, pak  umíme také najít øe¹ení tohoto problému. Proto¾e jak jinak bychom o daném problému mohli tvrdit, ¾e zaruèenì platí, kdy¾ bychom ho neumìli vyøe¹it.
  15
  16 \s{Pøíklad:} Mìjme èernou skøíòku (fungující v polynomiálním èase), která odpoví, zda daný graf má nebo nemá perfektní párování. Odebereme hranu a zeptáme se, jestli i tento nový graf má pefektní párovaní. Kdy¾ má, tak tato hrana nebyla potøebná pro párování, vyhodíme ji, proto¾e ji nepotøebujeme.
  17 Kdy¾ nemá (hrana patøí do ka¾dého párování), tak si danou hranu poznamenáme a odebereme nejen ji a její vrcholy ale také hrany, které do tìchto vrcholù vedly. Toto je korektní krok, proto¾e v pùvodním grafu tyto vrcholy byly navzájem spárované, a tedy nemohou být spárované s~¾ádnými jinými vrcholy.
  18 Takto iterujeme, dokud to jde. Výsledkem je mno¾ina hran, které patøí do perfektního párování. Tím jsme dané párování nalezli.
  19 Hran je polynomiálnì mnoho a skøíòka funguje v polynomiálním èase, tak¾e algoritmus je polynomiální.
  20
  21 \s{Definice:} Jsou-li $A$, $B$ rozhodovací problémy, pak øíkáme, ¾e $A$ lze {\I redukovat} (pøevést) na $B$ (pí¹eme $A \rightarrow B$) $\Leftrightarrow$ existuje funkce $f$ spoèitatelná v polynomiálním èase taková, ¾e pro $\forall x: A(x) = B(f(x))$.
  22
  23 \s{Pøíklad:} Hledání maximálního párování v bipartitním grafu $\rightarrow$ Hledání maximálního toku v síti.
  24 Funkce $f$ je funkce, která vezme bipartitní graf a vyrobí z~nìj sí» (jak správnì vyrobit sí» pro tento pøíklad viz 3.pøedná¹ka - Dinicùv algoritmus).
  25
  26 \s{Nìco málo o slo¾itosti:}
  27 Kdy¾ $A$ lze redukovat na $B$ funkcí $f$ a vstup $A$ je $x$, t¾. $\vert x \vert = n$ a funkce $f$ je spoèitatelná v polynomiálním èase, t¾. $\vert f(x) \vert = \O(n^k)$ pro nìjaké $k$, pak B umíme vyøe¹it v èase $\O(\vert f(x)^l \vert) = \O(n^{kl})$, $f$ poèítá v polynomiálním èase $\rightarrow$ mù¾e vydat maximálnì polynomiální výstup.
  28
  29 $A \rightarrow B$ znamená, ¾e $B$ je alespoò tak tì¾ké jako $A$.
  30
  31 \s{Pozorování:} Pøevoditelnost je:
  32 \itemize\ibull
  33 \:reflexivní (úlohu mù¾eme identicky pøevést na tu stejnou), $A \rightarrow A$,
  34 \:tranzitivní, $A \rightarrow B$ funkcí $f$, $B \rightarrow C$ funkcí $g$, $A \rightarrow C$ slo¾enou funkcí $(g \circ f)$.
  35 \endlist
  36
  37 \h{1. problém: SAT}
  38 \>Splnitelnost logických formulí, tj. dosazení $true$ èi $false$ za promìnné v logické formuli tak, aby formule dala výsledek $true$.
  39
  40 \>Zamìøíme se na speciální formu zadání formulí,  {\I konjunktivní normální formu} (CNF).
  41 $$(\ldots\lor\ldots\lor\ldots\lor\ldots) \land (\ldots\lor\ldots\lor\ldots\lor\ldots) \land \ldots $$
  42
  43 \>{\I Vstup:} Formule $\phi$ v konjunktivní normální formì.
  44
  45 \>{\I Výstup} $\exists$ dosazení $true$ a $false$ za promìnné takové, ¾e hodnota formule $\phi(\ldots) = true$.
  46
  47 \>Pro formuli platí následující podmínky:
  48
  49 \itemize\ibull
  50 \:{\I formule} je zadána pomocí {\I klauzulí} oddìlených $\land$,
  51 \:ka¾dá {\I klauzule} je slo¾ená z {\I literálù} oddìlených $\lor$,
  52 \:ka¾dý {\I literál} je buïto promìnná nebo její negace.
  53 \endlist
  54
  55 \>Uká¾eme, ¾e staèí vyøe¹it jednodu¹¹í problém 3-SAT.
  56
  57 \h{2. problém: 3-SAT}
  58 \s{Definice:} 3-SAT je takový SAT, v nìm¾ ka¾dá klauzule obsahuje nejvý¹e tøi literály.
  59
  60 \s{Pøevod 3-SAT na SAT:}
  61 Vstup není potøeba nijak upravovat, 3-SAT splòuje vlastnosti SATu, proto 3-SAT = SAT (3-SAT je alespoò tak tì¾ký jako SAT)
  62
  63 \s {Pøevod SAT na 3-SAT:}
  64 Musíme formuli pøevést tak, abychom neporu¹ili splnitelnost.
  65
  66 \>Trik pro dlouhé klauzule:
  67 $$(\alpha \lor \beta) \hbox{, t¾. } \vert\alpha\vert + \vert\beta\vert \ge 4$$
  68 pøepí¹eme na: $$(\alpha \lor x) \land (\beta \lor \lnot x),$$
  69 kde $x$ je nová promìnná, kterou nastavíme tak, abychom neovlivnili splnitelnost formule.
  70
  71 \>Platí-li:
  72 \itemize\ibull
  73 \:$\alpha \Rightarrow x = 0$ (zajistí splnìní druhé poloviny nové formule),
  74 \:$\beta \Rightarrow x = 1$ (zajistí splnìní první poloviny nové formule),
  75 \:$\alpha ,\beta / \lnot\alpha ,\lnot\beta \Rightarrow x = 0/1$ (je nám to jedno, celkové øe¹ení nám to neovlivní).
  76 \endlist
  77
  78 \>Tento trik opakujeme tak dlouho, dokud je to tøeba.
  79
  80 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.
  81
  82 \s{Poznámka:} U~3-SAT lze vynutit právì tøi literály, pro krátké klauzule pou¾ijeme následující trik:
  83 $$(\alpha) \rightarrow (\alpha \lor x) \land (\alpha \lor \lnot x).$$
  84
  85 \h{3. problém: Hledání nezávislé mno¾iny v grafu}
  86
  87 \>Existuje nezávislá mno¾ina vrcholù z~$G$ velikosti alespoò $k$?
  88
  89 \s{Definice:} {\I Nezávislá mno¾ina} (NzMna) je tvoøena vrcholy grafu, které nemají ¾ádnou spoleènou hranu.
  90
  91 \figure{nezmna.eps}{Pøíklad nezávislé mno¾iny.}{3in}
  92
  93 \>{\I Vstup:} Neorientovaný graf G, $k \in {\bb N}$.
  94
  95 \>{\I Výstup:} $\exists A \subseteq V(G)$, $\vert A \vert \ge k$: $\forall u,v \in A \Rightarrow uv \not\in E(G)$?
  96
  97 \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.
  98
  99 \>Uká¾eme, jak tento probém pøevést na 3-SAT.
 100
 101 \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$.
 102
 103 \s{Pøíklad:}
 104 $(x \lor y \lor z) \land (x \lor \lnot y \lor \lnot z) \land (\lnot x \lor \lnot y \lor p) $.
 105
 106 \>Pro ka¾dou klauzuli sestrojíme graf (trojúhelník) a pøidáme \uv{konfliktní} hrany, tj. $x$ a $\lnot x$.
 107
 108 Princip je takový, ¾e z~ka¾dé klauzule si vybereme promìnnou, která danou klauzuli splní, a to, aby promìnné, které si vybereme, nekolidovaly, vyøe¹íme hranami mezi promìnnými a jejich negacemi.
 109
 110 \figure{nezmna_graf.eps}{Ukázka pøevodu 3-SAT na nezávislou mno¾inu.}{3in}
 111
 112 Existuje nezávislá mno¾ina velikosti rovné poètu klauzulí?
 113 Pokud ano, tak dostaneme seznam promìnných, pomocí kterých splníme danou formuli.
 114
 115 \s{Pøevod NzMna na SAT:}
 116 Máme promìnné $v_1, \ldots , v_n$ pro vrcholy.
 117
 118 \>Nyní uká¾eme, jak pøevést problém hledání nezávislé mno¾iny, na SAT.
 119
 120 \itemize\ibull
 121 \:Poøídíme si promìnné $v_1, \ldots, v_n$ odpovídající vrcholùm grafu. Promìnná $v_i$ bude
 122   indikovat, zda se $i$-tý vrchol vyskytuje v~nezávislé mno¾inì.
 123 \:Pro ka¾dou hranu $ij \in E(G)$ pøidáme klauzuli $(\lnot v_i \lor \lnot v_j)$. Tyto klauzule
 124   nám ohlídají, ¾e vybraná mno¾ina je vskutku nezávislá.
 125 \:Je¹tì potøebujeme zkontrolovat, ¾e je mno¾ina dostateènì velká, tak¾e si její prvky
 126   oèíslujeme èísly od~1 do~$k$. Oèíslování popí¹eme maticí promìnných $x_{ij}$, pøièem¾
 127   $x_{ij}$ bude pravdivá právì tehdy, kdy¾ v~poøadí $i$-tý prvek nezávislé mno¾iny je vrchol~$v_j$.
 128 \:Pøidáme tedy klauzuje, které nám øeknou, ¾e vybrané do nezávislé mno¾iny jsou právì
 129   ty vrcholy, které jsou touto maticí oèíslované: $\forall i,j$, $x_{ij} \Rightarrow v_j$.
 130 \:Je¹tì potøebujeme zajistit, aby byla v~ka¾dém øádku i sloupci nejvý¹e jedna jednièka:
 131   $\forall j,i,i^{'}, i\ne i^{'} : x_{ij} \Rightarrow \lnot x_{i^{'}j}$ a
 132   $\forall i,j,j^{'}, j\ne j^{'} : x_{ij} \Rightarrow \lnot x_{ij^{'}}$.
 133 \:A~nakonec si ohlídáme, aby v~ka¾dém øádku byla alespoò jedna jednièka, klauzulí $\forall i :
 134   x_{i1} \lor x_{i2} \lor \ldots \lor x_{in}$.
 135 \endlist
 136
 137 \figure{matice.eps}{Výsledná matice.}{3in}
 138
 139 \h{4. problém: Klika}
 140
 141 \>{\I Vstup:} Graf $G, k \in N$.
 142
 143 \>{\I Výstup:} $\exists$ úplný podgraf grafu $G$ na $k$ vrcholech?
 144 \figure{klika.eps}{Pøíklad kliky.}{3in}
 145
 146 \s{Pøevod:} Prohodíme v grafu $G$ hrany a nehrany $\Rightarrow$ hledání nezávislé mno¾iny.
 147
 148 \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.
 149
 150 \figure{doplnek_nm.eps}{Prohození hran a nehran.}{3in}
 151
 152 \h{5. problém: 3D párování (3D matching)}
 153
 154 \>{\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).
 155
 156 \>{\I Výstup:} Perfektní podmno¾ina trojic - tj. taková podmno¾ina trojic, která obsahuje v¹echna $K$, $H$ a $Z$.
 157
 158 \>Uká¾eme, jak tento problém pøevést na 3,3-SAT (ov¹em to a¾ na dal¹í pøedná¹ce).
 159
 160 \figure{3d_parovani.eps}{Ukázka 3D párování.}{3in}
 161
 162
 163 \h{6. problém: 3,3-SAT}
 164 \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.
 165
 166 \s{Pøevod 3-SAT na 3,3-SAT:}
 167 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:
 168 $$
 169 (\lnot x_1 \lor x_2)
 170 (\lnot x_2 \lor x_3)
 171 (\lnot x_3 \lor x_4)
 172 \ldots
 173 (\lnot x_{k-1} \lor x_k)
 174 (\lnot x_k \lor x_1),
 175 $$
 176
 177 co¾ odpovídá:
 178
 179 $$
 180 (x_1 \Rightarrow x_2)
 181 (x_2 \Rightarrow x_3)
 182 (x_3 \Rightarrow x_4)
 183 \ldots
 184 (x_{k-1} \Rightarrow x_k)
 185 (x_k \Rightarrow x_1).
 186 $$
 187
 188 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 $2x$.
 189
 190 \s{Závìr:} Obrázek ukazuje problémy, jimi¾ jsme se dnes zabývali, a vztahy mezi tìmito problémy.
 191 \figure{prevody.eps}{Pøevody mezi problémy.}{3in}
 192
 193 \bye