+Nyní si uká¾eme, jak pøevést SAT na nìjaký problém. Kdy¾ chceme ukázat, ¾e na
+nìco se dá pøevést SAT, potøebujeme obvykle dvì vìci:
+konstrukci, která bude simulovat promìnné, tedy nìco, co nabývá dvou stavù
+\<true>/\<false>; a nìco, co bude reprezentovat klauzule a umí zaøídit, aby
+ka¾dá klauzule byla splnìna alespoò jednou promìnnou.
+Roz¹iøme tedy ná¹ katalog problémù o následující:
+\h{3D párování (3D matching)}
+
+\>{\I Vstup:} Tøi mno¾iny, napø. $K$ (kluci), $H$ (holky), $Z$ (zvíøátka) a
+mno¾ina $T$ kompatibilních trojic (tìch, kteøí se spolu snesou),
+ tj. $T \subseteq K\times H\times Z$.
+
+\>{\I Výstup:} Perfektní podmno¾ina trojic $P\subseteq K\times H \times Z$ --
+ tj. taková podmno¾ina trojic, ¾e $(\forall k\in K\ \exists !p\in P: k\in p)
+ \wedge(\forall h\in H\ \exists !p\in P: h\in p)
+ \wedge(\forall z\in Z\ \exists !p\in P: z\in p)$ -- tedy ka¾dý byl vybrán
+ právì jednou.
+
+
+\h{ Uká¾eme, jak na 3D-párování pøevést 3,3-SAT }
+
+Uva¾ujme takovouto konfiguraci:
+
+\fig{3d.eps}{4cm}
+
+\>4 zvíøátka, 2 kluci, 2 dívky a 4 trojice, které oznaèíme $A, B, C, D$.
+Je¹tì pøedpokládáme, ¾e zvíøátka
+ se mohou úèastnit nìjakých jiných trojic, ale
+tito ètyøi lidé se vyskytují pouze v~tìchto ètyøech trojicích a~nikde jinde.
+V¹imneme si, ¾e existují právì dvì mo¾nosti, jak tento obrázek spárovat.
+Abychom spárovali kluka $k_1$, tak si musíme vybrat $A$ nebo $B$. Kdy¾ si
+vybereme $A$, $k_1$ i $d_2$ u¾ jsou spárovaní tak¾e si nesmíme vybrat $B$ ani
+$D$. Pak jediná mo¾nost, jak spárovat $d_1$ a~$k_2$ je $C$. Jedna mo¾nost je
+tedy vybrat si $A$ a $C$ a jeliko¾ je obrázek symetrický, tak kdy¾ vybereme
+místo $A$ trojici $B$, dostaneme $B$ a~$D$. V¾dy si tedy vybereme dvì protìj¹í
+trojice v~obrázku.
+
+Tyto konfigurace budeme pou¾ívat k~reprezentaci promìnných. Pro ka¾dou
+promìnnou si nakreslíme takový obrázek a~to, ¾e $A$ bude spárované s~$C$, bude
+odpovídat tomu, ¾e $x=1$, a~spárování $B$ a~$D$ bude odpovídat
+ $x=0$. Pokud jsme
+pou¾ili $A$ a~$C$, zvíøata se sudými èísly, tj. $z_2$ a~$z_4$, horní a~dolní,
+jsou nespárovaná a~pokud jsme pou¾ili $B$ a~$D$, zvíøátka $z_1$ a~$z_3$ zùstala
+nespárovaná. Pøes tato nespárovaná zvíøátka mù¾eme pøedávat informaci, jestli
+promìnná $x$ má hodnotu \<true> nebo \<false> do dal¹ích èástí vstupu.
+
+Zbývá vymyslet, jak reprezentovat klauzule. Klauzule jsou trojice popø. dvojice
+literálù, napø. $\kappa = (x \lor y \lor \lnot r)$, kde
+potøebujeme zajistit, aby $x$ bylo nastavené na $1$ nebo $y$ bylo nastavené
+na~$1$ nebo $r$ na $0$.
+
+\fig{klauzule.eps}{4cm}
+
+\>Pro takovouto klauzuli si poøídíme dvojici kluk-dívka, kteøí budou figurovat
+ve tøech trojicích se tøemi rùznými zvíøátky, co¾ mají být volná zvíøátka
+z~obrázkù pro pøíslu¹né promìnné (podle toho, má-li se promìnná vyskytnout
+s negací nebo ne). A~zaøídíme to tak, aby ka¾dé zvíøátko bylo
+pou¾ité maximálnì v~jedné takové trojici, co¾ jde proto, ¾e ka¾dý literál se
+vyskytuje maximálnì dvakrát a~pro ka¾dý literál máme dvì volná zvíøátka,
+z~èeho¾ plyne, ¾e zvíøátek je dost pro v¹echny klauzule. Pro dvojice se postupuje
+obdobnì.
+
+Je¹tì nám ale urèitì zbude $2p-k$ zvíøátek, kde $p$ je poèet promìnných, $k$
+poèet klauzulí -- ka¾dá promìnná vyrobí 4 zvíøátka, klauzule zba¹tí jedno
+a samotné ohodnocení 2 zvíøátka -- tak pøidáme je¹tì $2p-k$ párù
+kluk-dìvèe, kteøí milují
+v¹echna zvíøátka, a~ti vytvoøí zbývající trojice.
+
+Pokud formule byla splnitelná, pak ze splòujícího ohodnocení mù¾eme vyrobit
+párování s~na¹í konstrukcí. Obrázek pro ka¾dou promìnnou spárujeme podle
+ohodnocení, tj. promìnná je $0$ nebo $1$ a~pro ka¾dou klauzuli si vybereme
+nìkterou z~promìnných, kterými je ta klauzule splnìna. Funguje to ale
+i~opaènì: Kdy¾ nám nìkdo dá párovaní v~na¹í konstrukci, pak z nìho doká¾eme
+vyrobit splòující ohodnocení dané formule. Podíváme se, v~jakém stavu je
+promìnná, a~to je v¹echno. Z~toho, ¾e jsou správnì spárované klauzule, u¾
+okam¾itì víme, ¾e jsou v¹echny splnìné.
+
+Zbývá ovìøit, ¾e na¹e redukce funguje v~polynomiálním èase. Pro ka¾dou klauzuli
+spotøebujeme konstantnì mnoho èasu, $2p-k$ je také polynomiálnì mnoho a~kdy¾ v¹e
+seèteme, máme polynomiální èas vzhledem k~velikosti vstupní formule. Tím je
+pøevod hotový a~mù¾eme 3D-párování zaøadit mezi NP-úplné problémy.