\input lecnotes.tex

\prednaska{10}{Pøevody problémù}{(zapsali Martin Chytil, Vladimír Kudelas)}

\>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$.]

\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ý, 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 pøevést) na $B$ (pí¹eme $A \rightarrow B$) $\Leftrightarrow$
existuje funkce $f$ spoèitatelná v polynomiálním èase taková, ¾e pro $\forall
x: A(x) = B(f(x))$.

V¹imnìte si, ¾e $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)$, tak¾e $B(f(x))$
pobì¾í v~èase $\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

\>Podívejme se nyní na~pøevody mezi dal¹ími zajímavými problémy:

\h{1. problém: SAT}
\>Splnitelnost logických formulí, tj. dosazení \<true> èi \<false> za promìnné v logické formuli tak, aby formule dala výsledek \<true>.

\>Zamìøíme se na speciální formu zadání formulí,  {\I konjunktivní normální formu} (CNF).
$$(\ldots\lor\ldots\lor\ldots\lor\ldots) \land (\ldots\lor\ldots\lor\ldots\lor\ldots) \land \ldots $$

\>{\I Vstup:} Formule $\varphi$ v konjunktivní normální formì.

\>{\I Výstup:} $\exists$ dosazení \<true> a \<false> za promìnné takové, ¾e hodnota formule $\varphi(\ldots) = \<true>$.

\>Pro formuli platí následující podmínky:

\itemize\ibull
\:{\I formule} je zadána pomocí {\I klauzulí} 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

\>Uká¾eme, ¾e staèí vyøe¹it jednodu¹¹í problém 3-SAT.

\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{Pøevod 3-SAT na SAT:}
Vstup není potøeba nijak upravovat, 3-SAT splòuje vlastnosti SATu, proto 3-SAT $\rightarrow$ 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.

\>Trik pro dlouhé klauzule: Ka¾dou klauzuli
$$(\alpha \lor \beta) \hbox{, t¾. } \vert\alpha\vert + \vert\beta\vert \ge 4$$
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

\>Tento trik opakujeme tak dlouho, dokud je to tøeba.

Nabízí se otázka, proè mù¾eme promìnnou $x$ nastavit, 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.

\s{Poznámka:} U~3-SAT lze vynutit právì tøi literály, pro krátké klauzule pou¾ijeme následující trik:
$$(\alpha) \rightarrow (\alpha \lor x) \land (\alpha \lor \lnot x).$$

\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 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)$?

\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.

\>Uká¾eme, jak na~tento probém pøevést 3-SAT.

\s{Pøevod:} 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) $.

\>Pro ka¾dou klauzuli sestrojíme graf (trojúhelník) a pøidáme \uv{konfliktní} hrany, tj. $x$ a $\lnot x$.

Princip je takový, ¾e z~ka¾dé klauzule si vybereme literál, který danou
klauzuli splní, a to tak, aby literály, které si vybereme, nekolidovaly. Kolize
o¹etøíme hranami mezi promìnnými a jejich negacemi.

\figure{nezmna_graf.eps}{Ukázka pøevodu 3-SAT na nezávislou mno¾inu}{3in}

Existuje nezávislá mno¾ina velikosti rovné poètu klauzulí?
Pokud ano, tak dostaneme seznam promìnných, pomocí kterých splníme danou formuli.

\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
  indikovat, zda se $i$-tý vrchol vyskytuje v~nezávislé mno¾inì.
\: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 klauzuje, 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$.
\: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

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

\h{4. problém: Klika}

\>{\I Vstup:} Graf $G, k \in N$.

\>{\I Výstup:} $\exists$ úplný podgraf grafu $G$ na $k$ vrcholech?
\figure{klika.eps}{Pøíklad kliky}{2in}

\s{Pøevod:} Prohodíme v grafu $G$ hrany a nehrany $\Rightarrow$ hledání nezávislé mno¾iny.

\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.

\figure{doplnek_nm.eps}{Prohození hran a nehran}{2in}

\h{5. 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 tento problém pøevést na 3,3-SAT (ov¹em to a¾ na dal¹í pøedná¹ce).

\figure{3d_parovani.eps}{Ukázka 3D párování}{3in}


\h{6. 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:
$$
(\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).
$$

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á 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ì.

\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
