+\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 $$