From 665d33beeafeb38c0b3aacefeadb73764ff9e6a6 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 14 Dec 2009 19:45:31 +0100 Subject: [PATCH] Revize prevodu. --- 10-prevody/10-prevody.tex | 79 ++++++++++++++++++++------------------- 1 file changed, 41 insertions(+), 38 deletions(-) diff --git a/10-prevody/10-prevody.tex b/10-prevody/10-prevody.tex index 2f7a3f3..b30e31e 100644 --- a/10-prevody/10-prevody.tex +++ b/10-prevody/10-prevody.tex @@ -11,8 +11,9 @@ pracuj a místo $L(x)=\hbox{\sc ano}$ psát prostì $x\in L$.] Vstupy mìjme zakódované jen pomocí nul a jednièek (obecnì je jedno, jaký základ pro soustavu -kódování zvolíme, pøevody mezi poyladickými soustavami jsou co do velikosti polynomiální). Rozhodovací problém -zadefinujeme jako $f:\ \{0,1\}^{\ast} \to \{0,1\}$, to jest funkci z mno¾iny v¹ech øetìzcù jednièek a nul +kódování zvolíme, pøevody mezi soustavami o nìjakém základu $\neq$ 1 jsou co do velikosti +zápisu polynomiální). Rozhodovací problém je tedy +$f:\ \{0,1\}^{\ast} \to \{0,1\}$, to jest funkce z mno¾iny v¹ech øetìzcù jednièek a nul do mno¾iny $\{1,0\}$, kde 1 na výstupu znamená {\sc ano}, 0 {\sc ne}. \s{Pøíklad:} Je dán bipartitní graf $G$ a $k \in {\bb N}$. Existuje v $G$ @@ -35,7 +36,7 @@ do hledan mnoho a skøíòka funguje v polynomiálním èase, tak¾e celý algoritmus je polynomiální. A~jak ná¹ rozhodovací problém øe¹it? Nejsnáze tak, ¾e ho pøevedeme -na~{jiný\footnote{${}^{\dag}$}{vìrni matfyzáckým vtipùm}}, který +na~{jiný,\footnote{${}^{\dag}$}{vìrni matfyzáckým vtipùm}} který u¾ vyøe¹it umíme. Tento postup jsme (právì u~hledání párování) u¾ pou¾ili v~kapitole o~Dinicovì algoritmu. Vytvoøili jsme vhodnou sí», pro kterou platilo, ¾e v~ní existuje tok velikosti~$k$ právì tehdy, kdy¾ @@ -44,8 +45,8 @@ v~p Takovéto pøevody mezi problémy mù¾eme definovat obecnì: \s{Definice:} Jsou-li $A$, $B$ rozhodovací problémy, pak øíkáme, ¾e $A$ lze {\I -redukovat} (neboli pøevést) na $B$ (pí¹eme $A \rightarrow B$) $\equiv$ -existuje funkce $f$ spoèitatelná v polynomiálním èase taková, ¾e pro $\forall +redukovat} (neboli {\it pøevést}) na $B$ (pí¹eme $A \rightarrow B$) právì tehdy, +kdy¾ existuje funkce $f$ spoèitatelná v polynomiálním èase taková, ¾e pro $\forall x: A(x) = B(f(x))$. V¹imnìme si, ¾e $f$ pracující v polynomiálním èase vstup zvìt¹í nejvíce polynomiálnì. @@ -54,9 +55,9 @@ jako probl lze tak øe¹it i~$A$): Nech» problém~$B$ umíme øe¹it v~èase $\O(b^k)$, kde $b$ je délka jeho vstupu. Nech» dále funkce $f$ pøevádìjící $A$ na $B$ pracuje v~èase $\O(a^\ell)$ pro vstup délky~$a$. Spustíme-li tedy $B(f(x))$ na~nìjaký -vstup~$x$ problému~$A$, bude mít $f(x)$ délku $\O(a^\ell)$, tak¾e $B(f(x))$ -pobì¾í v~èase $\O(a^\ell + (a^\ell)^k) = \O(a^{k\ell})$, co¾ je polynomiální -v~délce vstupu~$a$. +vstup~$x$ problému~$A$, bude mít $f(x)$ délku $\O(a^\ell)$, kde $a=|q|$; tak¾e +$B(f(x))$ pobì¾í v~èase $\O(a^\ell + (a^\ell)^k) = \O(a^{k\ell})$, co¾ je +polynomiální v~délce vstupu~$a$. \s{Pozorování:} Pøevoditelnost je @@ -71,7 +72,8 @@ v~p $A\rightarrow B$ a $B\rightarrow A$. Omezíme-li se v¹ak na tøídy navzájem pøevoditelných problémù, dostáváme ji¾ (èásteèné) uspoøádání. Existují i navzájem nepøevoditelné problémy -- napøíklad problém v¾dy odpovídající 1 a problém v¾dy odpovídající 0. -Podívejme se nyní na~pøevody mezi dal¹ími zajímavými problémy: +Nyní se ji¾ podíváme na nìjaké zajímavé problémy. Obecnì to budou problémy, na které +polynomiální algoritmus není znám, a vzájemnými pøevody zjistíme ¾e jsou stejnì tì¾ké. \h{1. problém: SAT} \>Splnitelnost (satisfiability) logických formulí, tj. dosazení 1 èi @@ -84,7 +86,7 @@ Pod \:ka¾dá {\I klauzule} je slo¾ená z {\I literálù} oddìlených $\lor$, \:ka¾dý {\I literál} je buïto promìnná nebo její negace. \endlist -formule mají tedy tvar: +\>Formule mají tedy tvar: $$\psi = (\ldots\lor\ldots\lor\ldots\lor\ldots) \land (\ldots\lor\ldots\lor\ldots\lor\ldots) \land \ldots $$ \>{\I Vstup:} Formule $\psi$ v konjunktivní normální formì. @@ -93,10 +95,10 @@ $$\psi = (\ldots\lor\ldots\lor\ldots\lor\ldots) \land (\ldots\lor\ldots\lor\ldot -\>Pøevod nìjaké obecné formule $\psi$ na jí ekvivalentní $\chi$ v CNF mù¾e +\>Pøevod nìjaké obecné formule $\psi$ na jí ekvivalentní $\chi$ v~CNF mù¾e zpùsobit, ¾e $\chi$ je exponenciálnì velká vùèi $\psi$. -Lze ov¹em podniknout pøevod na takovou formuli $\chi'$ v CNF, která sice není -ekvivalentní s $\psi$ (tedy ne ka¾dý model +Pozdìji uká¾eme, ¾e lze podniknout pøevod na takovou formuli $\chi'$ v~CNF, která sice není +ekvivalentní s $\psi$ (pøibydou nám promìnné, a ne ka¾dý roz¹íøený model $\psi$ je modelem $\chi'$), ale je splnitelná právì tehdy, kdy¾ je splnitelná $\psi$ --- co¾ nám pøesnì staèí --- a je lineárnì velká vùèi $\psi$. @@ -114,25 +116,26 @@ Mus $$(\alpha \lor \beta) \hbox{, t¾. } \vert\alpha\vert + \vert\beta\vert \ge 4 ,\ \vert\alpha\vert \geq 2,\ \vert\beta\vert\geq 2$$ pøepí¹eme na: $$(\alpha \lor x) \land (\beta \lor \lnot x),$$ -kde $x$ je nová promìnná, kterou nastavíme tak, abychom neovlivnili splnitelnost formule. - -\>Platí-li: -\itemize\ibull -\:$\alpha \Rightarrow x = 0$ (zajistí splnìní druhé poloviny nové formule), -\:$\beta \Rightarrow x = 1$ (zajistí splnìní první poloviny nové formule), -\:$\alpha ,\beta / \lnot\alpha ,\lnot\beta \Rightarrow x = 0/1$ (je nám to jedno, celkové øe¹ení nám to neovlivní). -\endlist +kde $x$ je nová promìnná (pøi ka¾dém dìlení klauzule {\it jiná} +nová promìnná). +%kterou nastavíme tak, abychom neovlivnili splnitelnost formule. \>Tento trik opakujeme tak dlouho, dokud je to tøeba -- formuli délky $k+l$ roztrhneme na formule délky $k+1$ a $l+1$. Pokud klauzule pùlíme, dostaneme polynomiální èas (strom rekurze má logaritmicky pater -- formule délky alespoò 6 se nám pøi rozdìlení zmen¹í na dvì instance velikosti maximálnì $2/3$ pùvodní, krat¹í formule nás netrápí; na ka¾dém patøe se vykoná tolik co na pøedchozím + $2^{hloubka}$ -za pøidané formule). Velikost výsledné formule je polynomiální vùèi pùvodní: -¾ádný literál (výskyt promìnné) pùvodní klauzule neduplikujeme, a v nejhor¹ím -pøípadì zùstane ka¾dý pùvodní literál v klauzuli sám s nìjakými dvìma pøidanými -(klauzule o tøech pøidaných mù¾eme vypustit) -- tedy poèet literálu se -maximálnì ztrojnásobí. +za pøidané formule). Velikost výsledné formule je tím pádem polynomiální vùèi pùvodní: +v ka¾dém kroku se pøidají jen dva literály, tedy celkem {\it èas na pøevod}$\cdot +2$ nových. + +\>Platí-li: +\itemize\ibull +\:$\alpha \Rightarrow$ zvolíme $x = 0$ (zajistí splnìní druhé poloviny nové formule), +\:$\beta \Rightarrow$ zvolíme $x = 1$ (zajistí splnìní první poloviny nové formule), +\:$\alpha ,\beta / \lnot\alpha ,\lnot\beta \Rightarrow$ zvolíme $x = 0/1$ (je nám to + jedno, celkové øe¹ení nám to neovlivní). +\endlist Nabízí se otázka, proè mù¾eme pøidanou promìnnou $x$ nastavovat, jak se nám zlíbí. Vysvìtlení je prosté -- promìnná $x$ nám pùvodní formuli nijak neovlivní, proto¾e @@ -151,7 +154,7 @@ takov \figure{nezmna.eps}{Pøíklad nezávislé mno¾iny}{1in} -\>{\I Vstup:} Neorientovaný graf G, $k \in {\bb N}$. +\>{\I Vstup:} Neorientovaný graf $G$, $k \in {\bb N}$. \>{\I Výstup:} $\exists A \subseteq V(G)$, $\vert A \vert \ge k$: $\forall u,v \in A \Rightarrow uv \not\in E(G)$? @@ -159,7 +162,8 @@ takov \>Uká¾eme, jak na~tento probém pøevést 3-SAT. -\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$. +\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$. \s{Pøíklad:} $(x \lor y \lor z) \land (x \lor \lnot y \lor \lnot z) \land (\lnot x \lor \lnot y \lor p) $. @@ -172,7 +176,9 @@ Existuje-li v grafu nez vybere právì jeden vrchol, a pøitom ¾ádné dva vrcholy nebudou odpovídat literálu a jeho negaci -- tedy dostaneme ohodnocení promìnných splòujících alespoò $k$ klauzulí. Na druhou stranu, existuje-li ohodnocení $k$ klauzulí, pak pøímo odpovídá nezávislé -mno¾inì velikosti $k$. Ptáme-li se tedy na nezávislou mno¾inu velikosti odpovídající +mno¾inì velikosti $k$ (v ka¾dém trojúhelníku zvolíme právì jednu z ohodnocených +promìnných, nemù¾e se stát ¾e zvolíme vrcholy konfliktní hrany). Ptáme-li se tedy +na nezávislou mno¾inu velikosti odpovídající poètu klauzulí, dostaneme odpovìï {\sc ano} právì tehdy, kdy¾ je formule splnitelná. Jsou-li ve formuli i klauzule krat¹í ne¾ 3, mù¾eme je buïto prodlou¾it metodou vý¹e @@ -182,9 +188,6 @@ vadit nebudou. \figure{nezmna_graf.eps}{Ukázka pøevodu 3-SAT na nezávislou mno¾inu}{3in} \s{Pøevod NzMna na SAT:} -Máme promìnné $v_1, \ldots , v_n$ pro vrcholy. - -\>Nyní uká¾eme, jak pøevést problém hledání nezávislé mno¾iny, na SAT. \itemize\ibull \:Poøídíme si promìnné $v_1, \ldots, v_n$ odpovídající vrcholùm grafu. Promìnná $v_i$ bude @@ -204,15 +207,15 @@ M \:A~nakonec si ohlídáme, aby v~ka¾dém øádku byla alespoò jedna jednièka, klauzulí $\forall i : x_{i1} \lor x_{i2} \lor \ldots \lor x_{in}$. \endlist -Takovýto pøevod je zøejmì polynomiální. +Tímto vynutíme NezMnu $\geq k$, co¾ jsme pøesnì chtìli. Takovýto pøevod je zøejmì polynomiální. \s{Pøíklad matice:} Jako pøíklad pou¾ijeme nezávislou mno¾inu z ukázky nezávislé mno¾iny. -Nech» jsou vrcholy grafu oèíslované zleva a ze zhora. Hledáme nezávislou mno¾inu velikosti $2$. +Nech» jsou vrcholy grafu oèíslované zleva a zezhora. Hledáme nezávislou mno¾inu velikosti $2$. Matice pak bude vypadat následovnì: $$ \pmatrix{1&0&0&0&0 \cr 0&0&0&1&0}$$ \s{Vysvìtlení:} Jako první vrchol mno¾iny bude vybrán vrchol $v_1$, proto v prvním -øádku a v prvním sloupci bude $1$. Jako druhý ($k$-tý) vrchol mno¾iny bude vybrán -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$. +øádku a v prvním sloupci bude $1$. Jako druhý vrchol mno¾iny bude vybrán +vrchol $v_4$, proto na druhém øádku a ve ètvrtém sloupci bude $1$. Na ostatních místech bude $0$. \h{4. problém: Klika} @@ -266,9 +269,9 @@ vyskytovat jak pozitivn \>{\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). -\>{\I Výstup:} Perfektní podmno¾ina trojic - tj. taková podmno¾ina trojic, která obsahuje v¹echna $K$, $H$ a $Z$. +\>{\I Výstup:} Perfektní podmno¾ina trojic -- tj. taková podmno¾ina trojic, která obsahuje v¹echna $K$, $H$ a $Z$. -\>Uká¾eme, jak tento problém pøevést na 3,3-SAT (ov¹em to a¾ na dal¹í pøedná¹ce). +\>Uká¾eme, jak na tento problém pøevést 3,3-SAT (ov¹em to a¾ na dal¹í pøedná¹ce). \figure{3d_parovani.eps}{Ukázka 3D párování}{3in} -- 2.39.2