-\input ../lecnotes.tex
+\input lecnotes.tex
+
+\prednaska{10}{Pøevody problémù}{\vbox{\hbox{(zapsali Martin Chytil, Vladimír Kudelas,}\hbox{ Michal Kozák, Vojta Tùma)}}}
+
+\>Na této pøedná¹ce se budeme zabývat rozhodovacími problémy a jejich obtí¾ností.
+Za jednoduché budeme trochu zjednodu¹enì pova¾ovat ty problémy, na~nì¾ známe algoritmus
+pracující v~polynomiálním èase.
+
+\s{Definice:} {\I Rozhodovací problém} je takový problém, jeho¾ výstupem je v¾dy {\sc ano}, nebo {\sc ne}.
+[Formálnì bychom se na~nìj mohli dívat jako na~mno¾inu $L$ vstupù, na~které je odpovìï {\sc ano},
+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 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$
+párování, které obsahuje alespoò $k$ hran?
+
+To, co bychom ve~vìt¹inì pøípadù chtìli, je samozøejmì nejen zjistit, zda takové párování
+existuje, ale také nìjaké konkrétní najít. V¹imnìme si ale, ¾e kdy¾ umíme rozhodovat
+existenci párování v~polynomiálním èase, mù¾eme ho polynomiálnì rychle i najít:
+
+Mìjme èernou skøíòku (fungující v polynomiálním èase), která odpoví, zda daný
+graf má nebo nemá párování o~$k$ hranách. Odebereme z~grafu libovolnou hranu
+a zeptáme se, jestli i tento nový graf má párovaní velikosti~$k$. Kdy¾ má, pak tato
+hrana nebyla pro existenci párování potøebná, a~tak ji odstraníme. Kdy¾ naopak
+nemá (hrana patøí do ka¾dého párování po¾adované velikosti), 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.
+Na~nový graf aplikujeme znovu tentý¾ postup. Výsledkem je mno¾ina hran, které patøí
+do hledaného párování. Hran, a tedy i iterací na¹eho algoritmu, je polynomiálnì
+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ý
+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¾
+v~pùvodním grafu existuje párování velikosti~$k$.
+
+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 {\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ì.
+
+\s{Pozorování:} $A\rightarrow B$ také znamená, ¾e problém~$B$ je alespoò tak tì¾ký
+jako problém~$A$ (tím myslíme, ¾e pokud lze $B$ øe¹it v~polynomiálním èase,
+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)$, 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
+\itemize\ibull
+\:reflexivní (úlohu mù¾eme pøevést na tu stejnou identickým zobrazením): $A \rightarrow A$,
+\:tranzitivní: Je-li $A \rightarrow B$ funkcí $f$, $B \rightarrow C$ funkcí $g$,
+pak $A \rightarrow C$ slo¾enou funkcí $g \circ f$
+(slo¾ení dvou polynomiálních funkcí je zase polynomiální funkce, jak u¾ jsme zpozorovali
+v~pøedchozím odstavci).
+\endlist
+\>Takovýmto relacím øíkáme kvaziuspoøádání -- nesplòují obecnì antisymetrii, tedy mù¾e nastat
+$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.
+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
+0 za promìnné v logické formuli tak, aby formule dala výsledek 1.
+
+\>Zamìøíme se na speciální formu zadání formulí, {\I konjunktivní normální formu} (CNF),
+ které splòují následující podmínky:
+\itemize\ibull
+\:{\I formule} je zadána pomocí {\I klauzulí}\footnote{${}^{\dag}$}{bez politických konotací} oddìlených $\land$,
+\: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:
+$$\psi = (\ldots\lor\ldots\lor\ldots\lor\ldots) \land (\ldots\lor\ldots\lor\ldots\lor\ldots) \land \ldots $$
-\prednaska{10}{Pøevody problémù}{(zapsali Martin Chytil, Vladimír Kudelas)}
+\>{\I Vstup:} Formule $\psi$ v konjunktivní normální formì.
-Na této pøedná¹ce se budeme zabývat rozhodovacími problémy a pøevody mezi nimy.
+\>{\I Výstup:} $\exists$ dosazení 1 a 0 za promìnné takové, ¾e hodnota formule $\psi(\ldots) = 1$.
-\s{Definice:} {\I Rozhodovací problém} je takový problém, jeho¾ výstupem je v¾dy {\sc ano} nebo {\sc ne}
-\s{Pøíklad:} Je dán bipartitní graf $G$, $k \in N$. Existuje v $G$ párování, které obsahuje alespoò $k$ hran?
-\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.
-Tzn. Existuje v síti $G$ tok velikosti alespoò $k$?
+\>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$.
+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$.
-\s{Obecnì se dá øici:} Pokud daný pro problém umíme rozhodnout, zda platí $\Rightarrow$ umíme najít øe¹ení problému.
-\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.
-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.
-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.
-Hran je polynomiálne mnoho a skøíòka funguje v polynomiálním èase, tak¾e algoritmus je polynomiální.
+\h{2. problém: 3-SAT}
+\s{Definice:} 3-SAT je takový SAT, v nìm¾ ka¾dá klauzule obsahuje nejvý¹e tøi literály.
-\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))$
+\s{Pøevod 3-SAT na SAT:}
+Vstup není potøeba nijak upravovat, 3-SAT splòuje vlastnosti SATu, proto 3-SAT
+$\rightarrow$ SAT (SAT je alespoò tak tì¾ký jako 3-SAT)
-\s{Pøíklad:} Bipartitní graf $\rightarrow$ Tok v síti
-funkce $f$ je funkce, která vezme bipartitní graf a vyrobí z nìj regulerní sí» (pøidá zdroj, stok, hrany + ohodnocení)
+\s {Pøevod SAT na 3-SAT:}
+Musíme formuli pøevést tak, abychom neporu¹ili splnitelnost.
-\s{Nìco málo o slo¾itosti:}
-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)$
-$ pro vstup x: \vert x \vert = n$
-$ \vert f(x)\vert = O(n^k)$ pro nìjaké k
-B poèíta v èase $O(n^{kl})$
-$f$ poèíta v polynomiálním èase $\rightarrow$ mù¾e vydat maximálne polynomiální výstup
+\>Trik pro dlouhé klauzule: Ka¾dou \uv{¹patnou} klauzuli
+$$(\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á (pøi ka¾dém dìlení klauzule {\it jiná}
+nová promìnná).
+%kterou nastavíme tak, abychom neovlivnili splnitelnost formule.
-\s{Pozorování:} funkce $f$ je:
-\itemize\ibull
-\:reflexivní (úlohu mù¾eme identicky pøevést na tu stejnou), $A \rightarrow A$
-\:tranzitivní, $A \rightarrow B$ funkcí $f$, $B \rightarrow C$ funkcí $g$, $A \rightarrow C$ slo¾enou funkcí $(f o g)$
-\endlist
+\>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 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.
-\h{1.Problém: SAT}
+\>Platí-li:
\itemize\ibull
-\:splnitelnost logických formulí
-\:tj. dosazení $0,1$ do logické formule tak, aby formule platila
+\:$\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
-Zamìøíme se na speciální formu zadání formulí - konjunktivní normální forma:
-$$(\ldots\lor\ldots\lor\ldots\lor\ldots\lor) \& (\ldots\lor\ldots\lor\ldots\lor\ldots\lor) \& \ldots $$
+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
+se v ní nevyskytuje, proto ji mù¾eme nastavit tak, jak chceme.
-{\I Vstup:} formule v konjunktivní normální formì (CNF)
-{\I Výstup} $\exists$ dosazení $0/1$ za promìnné t.¾. $\phi(\ldots) = 1$.
+\s{Poznámka:} U~3-SAT lze vynutit právì tøi literály, pro krátké klauzule
+pou¾ijeme stejný trik:
+$$(\alpha) \rightarrow (\alpha \vee \alpha) \rightarrow (\alpha \lor x) \land (\alpha \lor \lnot x).$$
-$$ \phi(x, y, \ldots) = (x \lor \lnot y \lor \ldots) \& (\ldots\lor\ldots\lor\ldots\lor\ldots\lor) \& \ldots $$
-\itemize\ibull
-\:formule zadána pomocí klauzulí oddìlených \&,
-\:ka¾dá klauzule je slo¾ená z literálù oddìlených $\lor$,
-\:ka¾dý literál je slo¾ený z promìnných, nebo $\lnot$ promìnných
-\endlist
-
-Uká¾eme, ¾e staèí vyøe¹it jednodu¹¹í problém 3-SAT.
-
-\h{2.Problém: 3-SAT}
-{\I 3-SAT} je SAT, kde ka¾dá klauzule obsahuje nejvý¹e 3 literály
-
-\s{Pøevod 3-SAT na SAT}
-platí identita, 3-SAT splòuje vlastnosti SATu, proto 3-SAT = SAT (3-SAT je alespoò tak tì¾ký, jako SAT)
-
-\s {Pøevod SAT na 3-SAT}
-- musíme formuli pøevést tak, abychom neporu¹ili splnitelnost
-{\I trik pro dlouhé klauzule:}
-$$(\alpha \lor \beta) t¾. \vert\alpha\vert + \vert\beta\vert \ge 4$$
-pøepí¹eme na: $$(\alpha \lor x) \& (\beta \lor \lnot x)$$
-$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í)
-Hodnota x nám pùvodní formuli nijak neovlivní, proto¾e se v ní nevyskytuje, proto ji mù¾eme nastavit, jak chceme my.
-Tento trik opakujeme tak dlouho, dokud je to tøeba.
+\h{3. problém: Hledání nezávislé mno¾iny v grafu}
+
+\>Existuje nezávislá mno¾ina vrcholù z~$G$ velikosti alespoò $k$?
+
+\s{Definice:} {\I Nezávislá mno¾ina} (NzMna) budeme øíkat ka¾dé mno¾inì vrcholù grafu
+takové, ¾e mezi nimi nevede ¾ádná hrana.
+
+\figure{nezmna.eps}{Pøíklad nezávislé mno¾iny}{1in}
-{\I poznámka} u 3-SAT lze vynutit právì $3$ literály, pro krátké klauzule pou¾ijeme následující trik:
-$$(a) \rightarrow (a \lor x) \& (a \lor \lnot x) $$
+\>{\I Vstup:} Neorientovaný graf $G$, $k \in {\bb N}$.
-\h{3. Problém: Hledání nezávislé mno¾iny v grafu}
-\s{Definice:} {\I Nezávislá mno¾ina:} je tvoøena vrcholy grafu, které spolu nemají spoleènou hranu
+\>{\I Výstup:} $\exists A \subseteq V(G)$, $\vert A \vert \ge k$: $\forall u,v \in A \Rightarrow uv \not\in E(G)$?
-{\I Vstup:} Neorientovaný graf G, $k \in N$
-{\I Výstup:} $\exists A \subseteq V(G)$, $\vert A \vert \ge k$, $u,v \in A \Rightarrow (uv) \not\in E(G)$ ?
+\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.
-Úlohu øe¹íme tak, ¾e problém 3-SAT pøevedeme tuto úlohu.
+\>Uká¾eme, jak na~tento probém pøevést 3-SAT.
-\s{poznámka:} Ka¾dý graf má minimálnì jednu nezávislou mno¾inu, a tou je prázdná mno¾ina.
-
-\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$
+\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) \& (x \lor \lnot y \lor \lnot z) \& (\lnot x \lor \lnot y \lor p) $$
-pro ka¾dou klauzuli sestrojíme graf (trojúhelník) + pøidáme "konfliktní" hrany 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) $.
-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.
+\>Pro ka¾dou klauzuli sestrojíme graf (trojúhelník) a pøidáme \uv{konfliktní}
+hrany, tj. $x$ a $\lnot x$. Poèet vrcholù grafu odpovídá poètu literálù ve formuli,
+poèet hran je maximálnì kvadratický a pøevod je tedy polynomiální.
-Existuje NzMna velikosti rovné poètu klauzulí?
-Pokud ano, tak dostaneme seznam promìnných, pomocí kterých splníme danou formuli.
+Existuje-li v grafu nezávislá mno¾ina velikosti $k$, pak z právì $k$ trojúhelníkù
+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$ (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á.
-\h{4. Problém: Klika}
-{\I Vstup:} Graf $G, k \in N$
-{\I Výstup:} $\exists$ úplný podgraf grafu $G$ na $k$ vrcholech ?
-\s{øe¹ení:} prohodíme hrany a nehrany $\rightarrow$ hledání nezávislé mno¾iny
-\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
+Jsou-li ve formuli i klauzule krat¹í ne¾ 3, mù¾eme je buïto prodlou¾it metodou vý¹e
+popsanou; nebo si v grafu necháme dvoj- a jedno-úhelníky, které ¾ádné z na¹ich úvah
+vadit nebudou.
-\s{Pøíklad:} (viz obrázky)
+\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
+\s{Pøevod NzMna na SAT:}
-pro ka¾dé $(i,j) \in E(G)$ pøidáme klauzuli $(\lnot vi \lor \lnot vj)$
+\itemize\ibull
+\:Poøídíme si promìnné $v_1, \ldots, v_n$ odpovídající vrcholùm grafu. Promìnná $v_i$ bude
+ indikovat, zda se $i$-tý vrchol vyskytuje v~nezávislé mno¾inì (tedy pøíslu¹né ohodnocení
+ promìnných bude vlastnì charakteristická funkce nezávislé mno¾iny).
+\:Pro ka¾dou hranu $ij \in E(G)$ pøidáme klauzuli $(\lnot v_i \lor \lnot v_j)$. Tyto klauzule
+ nám ohlídají, ¾e vybraná mno¾ina je vskutku nezávislá..
+\:Je¹tì potøebujeme zkontrolovat, ¾e je mno¾ina dostateènì velká, tak¾e si její prvky
+ oèíslujeme èísly od~1 do~$k$. Oèíslování popí¹eme maticí promìnných $x_{ij}$, pøièem¾
+ $x_{ij}$ bude pravdivá právì tehdy, kdy¾ v~poøadí $i$-tý prvek nezávislé mno¾iny je vrchol~$v_j$
+-- pøidáme tedy klauzule, které nám øeknou, ¾e vybrané do nezávislé mno¾iny jsou právì
+ ty vrcholy, které jsou touto maticí oèíslované: $\forall i,j$, $x_{ij} \Rightarrow v_j$
+ (jen dodejme, ¾e $a\Rightarrow b$ je definované jako $\neg a\vee b$).
+\:Je¹tì potøebujeme zajistit, aby byla v~ka¾dém øádku i sloupci nejvý¹e jedna jednièka:
+ $\forall j,i,i^{'}, i\ne i^{'} : x_{ij} \Rightarrow \lnot x_{i^{'}j}$ a
+ $\forall i,j,j^{'}, j\ne j^{'} : x_{ij} \Rightarrow \lnot x_{ij^{'}}$..
+\: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
+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 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ý 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}
-prvek matice $x_{i,j} = 1 \Leftrightarrow i$-tý prvek je vrchol $j$, tj. $\forall i,j$, $x_{ij} \Rightarrow v_j$
+\>{\I Vstup:} Graf $G, k \in N$.
-$\forall j,i,i^{'}, i\ne i^{'} : x_{ij} \Rightarrow x_{i^{'}j}$
+\>{\I Výstup:} $\exists$ úplný podgraf grafu $G$ na $k$ vrcholech?
+\figure{klika.eps}{Pøíklad kliky}{2in}
-$\forall i,j,j^{'}, j\ne j^{'} : x_{ij} \Rightarrow x_{ij^{'}}$
+\s{Pøevod:} Prohodíme v grafu $G$ hrany a nehrany $\Rightarrow$ (hledání nezávislé mno¾iny $\leftrightarrow$ hledání kliky).
+\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,
+ a naopak.
-\h{5. Problém: 3D -- párování (matching)}
-{\I Vstup:} Mno¾ina K, H, Z + mno¾ina kompatibilních 3-ic (ti, kteøí se spolu snesou)
-{\I Výstup:} Perfektní podmno¾ina 3-ic
-\s{Øe¹ení:} pøes 3,3-SAT (konkrétnìji viz dal¹í pøedná¹ka)
+\figure{doplnek_nm.eps}{Prohození hran a nehran}{2in}
-\h{3,3-SAT}
-\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
+\h{5. problém: 3,3-SAT}
+\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.
-\s{Pøevod 3-SAT na 3,3-SAT}
-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
+\s{Pøevod 3-SAT na 3,3-SAT:}
+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:
$$
-(\lnot x_1 \lor x_2)
-(\lnot x_2 \lor x_3)
-(\lnot x_3 \lor x_4)
-\ldots
-(\lnot x_{k-1} \lor x_k)
-(\lnot x_k \lor x_1)
+(\lnot x_1 \lor x_2),
+(\lnot x_2 \lor x_3),
+(\lnot x_3 \lor x_4),
+\ldots,
+(\lnot x_{k-1} \lor x_k),
+(\lnot x_k \lor x_1),
$$
co¾ odpovídá:
$$
-(x_1 \Rightarrow x_2)
-(x_2 \Rightarrow x_3)
-(x_3 \Rightarrow x_4)
-\ldots
-(x_{k-1} \Rightarrow x_k)
-(x_k \Rightarrow x_1)
+(x_1 \Rightarrow x_2),
+(x_2 \Rightarrow x_3),
+(x_3 \Rightarrow x_4),
+\ldots,
+(x_{k-1} \Rightarrow x_k),
+(x_k \Rightarrow x_1).
$$
-tímto zaruèíme, ¾e v¹echny promìnné budou mít stejnou hodnotu.
+
+Tímto zaruèíme, ¾e v¹echny nové promìnné budou mít stejnou hodnotu.
+
+Mimochodem, mù¾eme rovnou zaøídit, ¾e ka¾dý literál se vyskytuje nejvíce dvakrát (tedy ¾e
+ka¾dá promìnná se vyskytuje alespoò jednou pozitivnì a alespoò jednou negativnì). Pokud by
+se nìjaká promìnná objevila ve~tøech stejných literálech, mù¾eme na~ni
+také pou¾ít ná¹ trik a nahradit ji tøemi promìnnými. V~nových klauzulích se pak bude
+vyskytovat jak pozitivnì, tak negativnì.
+
+\h{6. problém: 3D párování (3D matching)}
+
+\>{\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$.
+
+\>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}
+
+\s{Závìr:} Obrázek ukazuje problémy, jimi¾ jsme se dnes zabývali, a vztahy mezi tìmito problémy.
+\figure{prevody.eps}{Pøevody mezi problémy}{3in}
\bye
projects / ads2.git / blobdiff