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 nimy.
   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 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$ (lze pøevést) $\rightarrow$ hledání maximálního toku.
  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 \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 tahle hrana nebyla potøebná pro párování, vyhodíme ji, proto¾e ji nepotøebujeme.
  16 Kdy¾ nemá (hrana patøí do párování), tak si danou hranu poznamenáme a odebereme ji i její vrcholy a také hrany, které vedli 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.
  17 Tohle 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.
  18 Hran je polynomiálne mnoho a skøíòka funguje v polynomiálním èase, tak¾e algoritmus je polynomiální.
  19
  20 \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, t¾. pro $\forall x: A(x) = B(f(x))$
  21
  22 \s{Pøíklad:} Bipartitní graf $\rightarrow$ Tok v síti
  23 funkce $f$ je funkce, která vezme bipartitní graf a vyrobí z nìj regulerní sí» (pøidá zdroj, stok, hrany + ohodnocení)
  24
  25 \s{Nìco málo o slo¾itosti:}
  26 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)$
  27 $ pro vstup x: \vert x \vert = n$
  28 $ \vert f(x)\vert = O(n^k)$ pro nìjaké k
  29 B poèíta v èase $O(n^{kl})$
  30 $f$ poèíta v polynomiálním èase $\rightarrow$ mù¾e vydat maximálne polynomiální výstup
  31
  32 \s{Pozorování:} funkce $f$ je:
  33 \itemize\ibull
  34 \:reflexivní (úlohu mù¾eme identicky pøevést na tu stejnou), $A \rightarrow A$
  35 \:tranzitivní, $A \rightarrow B$ funkcí $f$, $B \rightarrow C$ funkcí $g$, $A \rightarrow C$ slo¾enou funkcí $(f o g)$
  36 \endlist
  37
  38 \h{1.Problém: SAT}
  39 \itemize\ibull
  40 \:splnitelnost logických formulí
  41 \:tj. dosazení $0,1$ do logické formule tak, aby formule platila
  42 \endlist
  43
  44 Zamìøíme se na speciální formu zadání formulí - konjunktivní normální forma:
  45 $$(\ldots\lor\ldots\lor\ldots\lor\ldots\lor) \& (\ldots\lor\ldots\lor\ldots\lor\ldots\lor) \& \ldots $$
  46
  47 {\I Vstup:} formule v konjunktivní normální formì (CNF)
  48 {\I Výstup} $\exists$ dosazení $0/1$ za promìnné t.¾. $\phi(\ldots) = 1$.
  49
  50 $$ \phi(x, y, \ldots) = (x \lor \lnot y \lor \ldots) \& (\ldots\lor\ldots\lor\ldots\lor\ldots\lor) \& \ldots $$
  51 \itemize\ibull
  52 \:formule zadána pomocí klauzulí oddìlených \&,
  53 \:ka¾dá klauzule je slo¾ená z literálù oddìlených $\lor$,
  54 \:ka¾dý literál je slo¾ený z promìnných, nebo $\lnot$ promìnných
  55 \endlist
  56
  57 Uká¾eme, ¾e staèí vyøe¹it jednodu¹¹í problém 3-SAT.
  58
  59 \h{2.Problém: 3-SAT}
  60 {\I 3-SAT} je SAT, kde ka¾dá klauzule obsahuje nejvý¹e 3 literály
  61
  62 \s{Pøevod 3-SAT na SAT}
  63 platí identita, 3-SAT splòuje vlastnosti SATu, proto 3-SAT = SAT (3-SAT je alespoò tak tì¾ký, jako SAT)
  64
  65 \s {Pøevod SAT na 3-SAT}
  66 - musíme formuli pøevést tak, abychom neporu¹ili splnitelnost
  67 {\I trik pro dlouhé klauzule:}
  68 $$(\alpha \lor \beta) t¾. \vert\alpha\vert + \vert\beta\vert \ge 4$$
  69 pøepí¹eme na: $$(\alpha \lor x) \& (\beta \lor \lnot x)$$
  70 $x$ je nová promìnná, kterou nastavíme tak, abychom neovlivnili splnitelnost formule
  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 Hodnota x nám pùvodní formuli nijak neovlivní, proto¾e se v ní nevyskytuje, proto ji mù¾eme nastavit, jak chceme my.
  77 Tento trik opakujeme tak dlouho, dokud je to tøeba.
  78 \endlist
  79
  80 {\I poznámka} u 3-SAT lze vynutit právì $3$ literály, pro krátké klauzule pou¾ijeme následující trik:
  81 $$(a) \rightarrow (a \lor x) \& (a \lor \lnot x) $$
  82
  83 \h{3. Problém: Hledání nezávislé mno¾iny v grafu}
  84 \s{Definice:} {\I Nezávislá mno¾ina:} je tvoøena vrcholy grafu, které spolu nemají spoleènou hranu
  85
  86 {\I Vstup:} Neorientovaný graf G, $k \in N$
  87 {\I Výstup:} $\exists A \subseteq V(G)$, $\vert A \vert \ge k$, $u,v \in A \Rightarrow (uv) \not\in E(G)$ ?
  88
  89 Úlohu øe¹íme tak, ¾e problém 3-SAT pøevedeme tuto úlohu.
  90
  91 \s{poznámka:} Ka¾dý graf má minimálnì jednu nezávislou mno¾inu, a tou je prázdná mno¾ina.
  92
  93 \s{øe¹ení úlohy:} Z ka¾dé klauzule vybereme $1$ literál tak, abychom v rùzných klauzulích nevybírali konfliktnì, tj. $x a \lnot x$
  94
  95 \s {pøíklad}
  96 $$(x \lor y \lor z) \& (x \lor \lnot y \lor \lnot z) \& (\lnot x \lor \lnot y \lor p) $$
  97 pro ka¾dou klauzuli sestrojíme graf (trojúhelník) + pøidáme "konfliktní" hrany tj. $x a \lnot x$
  98
  99 Princip je takový, ¾e z ka¾dé klauzule si vybereme promìnnou, která danou klauzuli splní a to, aby promìnné, které si vybereme nekolidovali, vyøe¹íme hranami mezi promìnnými a jejich negacemi.
 100
 101 Existuje NzMna velikosti rovné poètu klauzulí?
 102 Pokud ano, tak dostaneme seznam promìnných, pomocí kterých splníme danou formuli.
 103
 104 \h{4. Problém: Klika}
 105 {\I Vstup:} Graf $G, k \in N$
 106 {\I Výstup:} $\exists$ úplný podgraf grafu $G$ na $k$ vrcholech ?
 107 \s{øe¹ení:} prohodíme hrany a nehrany $\rightarrow$ hledání nezávislé mno¾iny
 108 \s{dùvod:} pokud existuje úplný graf na $k$ vrcholech, tak v "invertovaném" grafu tyto vrcholy nejsou spojeny hranou, tj. tvoøí nezávislou mno¾inu
 109
 110 \s{Pøíklad:} (viz obrázky)
 111
 112 \s{Pøevod NzMna na SAT}
 113 Máme promìnné $v_1 \ldots v_n$ pro vrcholy
 114
 115 pro ka¾dé $(i,j) \in E(G)$ pøidáme klauzuli $(\lnot vi \lor \lnot vj)$
 116
 117
 118 prvek matice $x_{i,j} = 1 \Leftrightarrow i$-tý prvek je vrchol $j$, tj. $\forall i,j$, $x_{ij} \Rightarrow v_j$
 119
 120 $\forall j,i,i^{'}, i\ne i^{'} : x_{ij} \Rightarrow x_{i^{'}j}$
 121
 122 $\forall i,j,j^{'}, j\ne j^{'} : x_{ij} \Rightarrow x_{ij^{'}}$
 123
 124
 125 \h{5. Problém: 3D -- párování (matching)}
 126 {\I Vstup:} Mno¾ina K, H, Z + mno¾ina kompatibilních 3-ic (ti, kteøí se spolu snesou)
 127 {\I Výstup:} Perfektní podmno¾ina 3-ic
 128 \s{Øe¹ení:} pøes 3,3-SAT (konkrétnìji viz dal¹í pøedná¹ka)
 129
 130
 131 \h{3,3-SAT}
 132 \s{Definice:} {\I 3,3-SAT} je speciální pøípad 3-SATu, kde ka¾dá promìnná se vyskytuje v maximálnì 3 literálech
 133
 134 \s{Pøevod 3-SAT na 3,3-SAT}
 135 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
 136 $$
 137 (\lnot x_1 \lor x_2)
 138 (\lnot x_2 \lor x_3)
 139 (\lnot x_3 \lor x_4)
 140 \ldots
 141 (\lnot x_{k-1} \lor x_k)
 142 (\lnot x_k \lor x_1)
 143 $$
 144
 145 co¾ odpovídá:
 146
 147 $$
 148 (x_1 \Rightarrow x_2)
 149 (x_2 \Rightarrow x_3)
 150 (x_3 \Rightarrow x_4)
 151 \ldots
 152 (x_{k-1} \Rightarrow x_k)
 153 (x_k \Rightarrow x_1)
 154 $$
 155 tímto zaruèíme, ¾e v¹echny promìnné budou mít stejnou hodnotu.
 156
 157 \bye