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$, $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 síti $G$ tok velikosti alespoò $k$?
  13
  14 \s{Obecnì se dá øici:} Pokud daný pro problém umíme rozhodnout, zda platí $\Rightarrow$ umíme najít øe¹ení problému.
  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 párování), tak si danou hranu poznamenáme a odebereme ji i její vrcholy a také hrany, které vedly do tìchto vrcholù. 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 maximální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 redukovat na $B$ ($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:} Bipartitní graf $\rightarrow$ Tok v síti.
  24 Funkce $f$ je funkce, která vezme bipartitní graf a vyrobí z~nìj regulerní sí» (pøidá zdroj, stok, hrany a ohodnocení).
  25
  26 \s{Nìco málo o slo¾itosti:}
  27 Kdy¾ $A$ lze redukovat na $B$ a $B$ umíme vyøe¹it v èase $\O(\vert $vstup$ \vert^l) = \O(\vert f(x)\vert^l)$
  28  pro vstup $x: \vert x \vert = n$
  29 $ \vert f(x)\vert = \O(n^k)$ pro nìjaké $k$,
  30 $A$ poèítá v~èase $\O(n^{kl})$,
  31 $f$ poèítá v polynomiálním èase $\rightarrow$ mù¾e vydat maximálnì polynomiální výstup.
  32
  33 \s{Pozorování:} Funkce $f$ je:
  34 \itemize\ibull
  35 \:reflexivní (úlohu mù¾eme identicky pøevést na tu stejnou), $A \rightarrow A$,
  36 \:tranzitivní, $A \rightarrow B$ funkcí $f$, $B \rightarrow C$ funkcí $g$, $A \rightarrow C$ slo¾enou funkcí $(g \circ f)$.
  37 \endlist
  38
  39 \h{1. problém: SAT}
  40 \>Splnitelnost logických formulí, tj. dosazení $0$ èi $1$ do logické formule tak, aby formule platila.
  41
  42 \>Zamìøíme se na speciální formu zadání formulí,  {\I konjunktivní normální formu} (CNF):
  43 $$(\ldots\lor\ldots\lor\ldots\lor\ldots) \land (\ldots\lor\ldots\lor\ldots\lor\ldots) \land \ldots $$
  44
  45 \>{\I Vstup:} Formule v konjunktivní normální formì.
  46
  47 \>{\I Výstup} $\exists$ dosazení $0$ a $1$ za promìnné takové, ¾e hodnota formule $\phi(\ldots) = 1$.
  48
  49 $$ \phi(x, y, \ldots) = (x \lor \lnot y \lor \ldots) \land (\ldots\lor\ldots\lor\ldots\lor\ldots) \land \ldots $$
  50
  51 \>Pro formuli platí následující podmínky:
  52
  53 \itemize\ibull
  54 \:formule je zadána pomocí klauzulí oddìlených $\land$,
  55 \:ka¾dá klauzule je slo¾ená z literálù oddìlených $\lor$,
  56 \:ka¾dý literál je buïto promìnná nebo její negace.
  57 \endlist
  58
  59 \>Uká¾eme, ¾e staèí vyøe¹it jednodu¹¹í problém 3-SAT.
  60
  61 \h{2. problém: 3-SAT}
  62 \s{Definice:} 3-SAT je takový SAT, kde ka¾dá klauzule obsahuje nejvý¹e tøi literály.
  63
  64 \s{Pøevod 3-SAT na SAT:}
  65 Platí identita, 3-SAT splòuje vlastnosti SATu, proto 3-SAT = SAT (3-SAT je alespoò tak tì¾ký jako SAT)
  66
  67 \s {Pøevod SAT na 3-SAT:}
  68 Musíme formuli pøevést tak, abychom neporu¹ili splnitelnost.
  69
  70 \>Trik pro dlouhé klauzule:
  71 $$(\alpha \lor \beta) \hbox{, t¾. } \vert\alpha\vert + \vert\beta\vert \ge 4$$
  72 pøepí¹eme na: $$(\alpha \lor x) \land (\beta \lor \lnot x),$$
  73 kde $x$ je nová promìnná, kterou nastavíme tak, abychom neovlivnili splnitelnost formule.
  74
  75 \>Platí-li:
  76 \itemize\ibull
  77 \:$\alpha \Rightarrow x = 0$ (zajistí splnìní druhé poloviny nové formule),
  78 \:$\beta \Rightarrow x = 1$ (zajistí splnìní první poloviny nové formule),
  79 \:$\alpha ,\beta / \lnot\alpha ,\lnot\beta \Rightarrow x = 0/1$ (je nám to jedno, celkové øe¹ení nám to neovlivní).
  80
  81 Hodnota $x$ nám pùvodní formuli nijak neovlivní, proto¾e se v ní nevyskytuje, proto ji mù¾eme nastavit, jak chceme.
  82 \endlist
  83
  84 \>Tento trik opakujeme tak dlouho, dokud je to tøeba.
  85
  86 \s{Poznámka:} U~3-SAT lze vynutit právì tøi literály, pro krátké klauzule pou¾ijeme následující trik:
  87 $$(a) \rightarrow (a \lor x) \land (a \lor \lnot x).$$
  88
  89 \h{3. problém: Hledání nezávislé mno¾iny v grafu}
  90
  91 \>Existuje nezávislá mno¾ina vrcholù z~$G$ velikosti alespoò $k$?
  92
  93 \s{Definice:} {\I Nezávislá mno¾ina} (NzMna) je tvoøena vrcholy grafu, které spolu nemají spoleènou hranu.
  94
  95 \>{\I Vstup:} Neorientovaný graf G, $k \in N$.
  96
  97 \>{\I Výstup:} $\exists A \subseteq V(G)$, $\vert A \vert \ge k$, $u,v \in A \Rightarrow (uv) \not\in E(G)$?
  98
  99 \>Úlohu øe¹íme tak, ¾e problém 3-SAT pøevedeme tuto úlohu.
 100
 101 \s{Poznámka:} Ka¾dý graf má minimálnì jednu nezávislou mno¾inu, a tou je prázdná mno¾ina.
 102
 103 \s{Øe¹ení úlohy:} Z ka¾dé klauzule vybereme jeden literál tak, abychom v rùzných klauzulích nevybírali konfliktnì, tj. $x$ a $\lnot x$.
 104
 105 \s{Pøíklad:}
 106 $(x \lor y \lor z) \land (x \lor \lnot y \lor \lnot z) \land (\lnot x \lor \lnot y \lor p) $.
 107
 108 \>Pro ka¾dou klauzuli sestrojíme graf (trojúhelník) a pøidáme \uv{konfliktní} hrany, tj. $x$ a $\lnot x$.
 109
 110 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.
 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 \h{4. problém: Klika}
 116
 117 \>{\I Vstup:} Graf $G, k \in N$.
 118
 119 \>{\I Výstup:} $\exists$ úplný podgraf grafu $G$ na $k$ vrcholech?
 120
 121 \s{Øe¹ení:} Prohodíme hrany a nehrany $\rightarrow$ hledání nezávislé mno¾iny.
 122
 123 \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.
 124
 125 \s{Pøíklad:} (Viz obrázky.)
 126
 127 \s{Pøevod NzMna na SAT:}
 128 Máme promìnné $v_1, \ldots , v_n$ pro vrcholy.
 129
 130 \itemize\ibull
 131 \:Poøídíme si promìnné $v_1, \ldots, v_n$ odpovídající vrcholùm grafu. Promìnná $v_i$ bude
 132   indikovat, zda se $i$-tý vrchol vyskytuje v~nezávislé mno¾inì.
 133 \:Pro ka¾dou hranu $ij \in E(G)$ pøidáme klauzuli $(\lnot v_i \lor \lnot v_j)$. Tyto klauzule
 134   nám ohlídají, ¾e vybraná mno¾ina je vskutku nezávislá.
 135 \:Je¹tì potøebujeme zkontrolovat, ¾e je mno¾ina dostateènì velká, tak¾e si její prvky
 136   oèíslujeme èísly od~1 do~$k$. Oèíslování popí¹eme maticí promìnných $x_{ij}$, pøièem¾
 137   $x_{ij}$ bude pravdivá právì tehdy, kdy¾ v~poøadí $i$-tý prvek nezávislé mno¾iny je vrchol~$v_j$.
 138 \:Pøidáme tedy klauzuje, které nám øeknou, ¾e vybrané do nezávislé mno¾iny jsou právì
 139   ty vrcholy, které jsou touto maticí oèíslované: $\forall i,j$, $x_{ij} \Rightarrow v_j$.
 140 \:Je¹tì potøebujeme zajistit, aby byla v~ka¾dém øádku i sloupci nejvý¹e jedna jednièka:
 141   $\forall j,i,i^{'}, i\ne i^{'} : x_{ij} \Rightarrow \lnot x_{i^{'}j}$ a
 142   $\forall i,j,j^{'}, j\ne j^{'} : x_{ij} \Rightarrow \lnot x_{ij^{'}}$.
 143 \:A~nakonec si ohlídáme, aby v~ka¾dém øádku byla alespoò jedna jednièka, klauzulí $\forall i :
 144   x_{i1} \lor x_{i2} \lor \ldots \lor x_{in}$.
 145 \endlist
 146
 147
 148 \h{5. problém: 3D párování (3D matching)}
 149
 150 \>{\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).
 151
 152 \>{\I Výstup:} Perfektní podmno¾ina trojic.
 153
 154 \s{Øe¹ení:} Pøes 3,3-SAT (konkrétnìji, viz dal¹í pøedná¹ku).
 155
 156
 157 \h{6. problém: 3,3-SAT}
 158 \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.
 159
 160 \s{Pøevod 3-SAT na 3,3-SAT:}
 161 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:
 162 $$
 163 (\lnot x_1 \lor x_2)
 164 (\lnot x_2 \lor x_3)
 165 (\lnot x_3 \lor x_4)
 166 \ldots
 167 (\lnot x_{k-1} \lor x_k)
 168 (\lnot x_k \lor x_1),
 169 $$
 170
 171 co¾ odpovídá:
 172
 173 $$
 174 (x_1 \Rightarrow x_2)
 175 (x_2 \Rightarrow x_3)
 176 (x_3 \Rightarrow x_4)
 177 \ldots
 178 (x_{k-1} \Rightarrow x_k)
 179 (x_k \Rightarrow x_1).
 180 $$
 181
 182 Tímto zaruèíme, ¾e v¹echny promìnné budou mít stejnou hodnotu.
 183
 184 \bye