11-np/11-np.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{11}{NP-úplné problémy}{\vbox{\hbox{(zapsali F. Kaèmarik, R. Krivák, D. Remi¹}
   4         \hbox{ Michal Kozák, Vojta Tùma)}}}
   5
   6 Dosud jsme zkoumali problémy, které se nás ptaly na to, jestli nìco existuje.
   7 Napøíklad jsme dostali formuli a problém splnitelnosti se nás ptal, zda
   8 existuje ohodnocení promìnných takové, ¾e formule platí. Nebo v~pøípade
   9 nezávislých mno¾in jsme dostali graf a èíslo $k$ a ptali jsme se, jestli
  10 v~grafu existuje nezávislá mno¾ina, která obsahuje alespoò~$k$ vrcholù.
  11 Tyto otázky mìly spoleèné to, ¾e kdy¾ nám nìkdo napovìdìl nìjaký objekt, umìli
  12 jsme efektivnì øíci, zda je to ten, který hledáme. Napøíklad pokud dostaneme
  13 ohodnocení promìnných logické formule, staèí jen dosadit a spoèítat, kde
  14 formule dá \<true> nebo \<false>. Zjistit, ¾e nìjaký objekt je ten, který
  15 hledáme, umíme efektivnì. Tì¾ké na tom je takový objekt najít. Co¾ vede
  16 k~definici obecných vyhledávacích problémù, kterým se øíká tøída problémù NP.
  17 Nadefinujeme si ji poøádnì, ale nejdøíve zaèneme tro¹ièku jednodu¹¹í tøídou.
  18
  19 \s{Definice:} P je {\I tøída rozhodovacích problémù}, které jsou øe¹itelné
  20 v~polynomiálním èase. Jinak øeèeno, problém
  21 $L \in {\rm P}  \Leftrightarrow  \exists $ polynom $f$ a~$\exists$ algoritmus~$A$
  22 takový, ¾e $\forall x: L(x)=A(x)$ a $A(x)$ dobìhne v~èase $\O(f(x))$.
  23
  24 Tøída P tedy odpovídá tomu, o èem jsme se shodli, ¾e umíme efektivnì øe¹it.
  25 Nadefinujme nyní tøídu NP:
  26
  27 \s{Definice:} NP je {\I tøída rozhodovacích problémù} takových, ¾e $L \in {\rm NP}$ právì tehdy, kdy¾ $\exists $ problém
  28 $K\in{\rm P}$ a $\exists$  polynom  $g$ takový, ¾e pro
  29 $\forall x$ platí $L(x)=1  \Leftrightarrow  \exists $ nápovìda $ y: \vert y \vert \leq g(\vert x \vert)$ a souèasnì $K(x,y)=1$.
  30
  31 \s{Pozorování:} Splnitelnost logických formulí je v~NP. Staèí si toti¾ nechat napovìdìt, jak
  32 ohodnotit jednotlivé promìnné a pak ovìøit, jestli je formule splnìna. Nápovìda je polynomiálnì
  33 velká (dokonce lineárnì), splnìní zkontrolujeme také v~lineárním èase. Odpovíme tedy ano právì
  34 tehdy, existuje-li nápovìda, která nás pøesvìdèí, èili pokud je formule splnitelná.
  35
  36 \s{Pozorování:} Tøída P le¾í uvnitø NP.
  37 V~podstatì øíkáme, ¾e kdy¾ máme problém, který umíme øe¹it v~polynomiálním èase
  38 bez nápovìdy, tak to zvládneme v~polynomiálním èase i s~nápovìdou.
  39
  40 Problémy z minulé pøedná¹ky jsou v¹echny v NP (napø. pro nezávislou
  41 mno¾inu je onou nápovìdou pøímo mno¾ina vrcholù deklarující nezávislost),
  42 o jejich pøíslu¹nosti do P ale nevíme nic.
  43 Brzy uká¾eme, ¾e to jsou v jistém smyslu nejtì¾¹í problémy v~NP.
  44 Nadefinujme si:
  45
  46 \s{Definice:} Problém $L$ je NP-{\I tì¾ký} právì tehdy, kdy¾ je na~nìj pøevoditelný
  47 ka¾dý problém z~NP (viz definici pøevodù z minulé pøedná¹ky).
  48
  49 Rozmyslete si, ¾e pokud umíme øe¹it nìjaký NP-tì¾ký problém v~polynomiálním èase,
  50 pak umíme vyøe¹it v~polynomiálním èase v¹e v~NP, a tedy ${\rm P}={\rm NP}$.
  51
  52 My se budeme zabývat problémy, které jsou NP-tì¾ké a samotné jsou v~NP. Takovým problémùm se øíká NP-úplné.
  53
  54 \s{Definice:} Problém $L$ je NP-{\I úplný} právì tehdy, kdy¾ $L$ je NP-tì¾ký a $L \in {\rm NP}$.
  55
  56 NP-úplné problémy jsou tedy ve~své podstatì nejtì¾¹í problémy, které le¾í v~NP.
  57 Kdybychom umìli vyøe¹it nìjaký NP-úplný problém v~polynomiálním èase, pak
  58 v¹echno v~NP je øe¹itelné v~polynomiálním èase. Bohu¾el to, jestli nìjaký
  59 NP-úplný problém lze øe¹it v~polynomiálním èase, se neví. Otázka, jestli
  60 ${\rm P}={\rm NP}$, je asi nejznámìj¹í otevøený problém v~celé teoretické
  61 informatice.
  62
  63 Kde ale nìjaký NP-úplný problém vzít? K~tomu se nám bude velice hodit následující vìta:
  64
  65 \s{Vìta (Cookova):} SAT je NP-úplný.
  66
  67 \>Dùkaz je znaènì technický, pøibli¾nì ho naznaèíme pozdìji. Pøímým dùsledkem
  68 Cookovy vìty je, ¾e cokoli v~NP je pøevoditelné na SAT.
  69 K dokazování NP-úplnosti dal¹ích problémù pou¾ijeme následující vìtièku:
  70
  71 \s{Vìtièka:} Pokud problém $L$ je NP-úplný a $L$ se dá pøevést na nìjaký problém $M\in{\rm NP}$, pak $M$ je také NP-úplný.
  72
  73 \proof
  74 Tuto vìtièku staèí dokázat pro NP-tì¾kost, NP-úplnost plyne okam¾itì z~toho, ¾e
  75 problémy jsou NP-tì¾ké a le¾í v~NP (podle pøedpokladu).
  76
  77 Víme, ¾e $L$ se dá pøevést na~$M$ nìjakou funkcí~$f$. Jeliko¾ $L$ je NP-úplný,
  78 pak pro ka¾dý problém $Q\in{\rm NP}$ existuje nìjaká funkce~$g$, která pøevede
  79 $Q$ na~$L$. Staèí tedy slo¾it funkci~$f$ s~funkcí~$g$, èím¾ získáme funkci pracující
  80 opìt v~polynomiálním èase, která pøevede~$Q$ na~$M$. Ka¾dý problém z~NP se tedy
  81 dá pøevést na problém~$M$.
  82 \qed
  83
  84 \s{Dùsledek:} Cokoliv, na co jsme umìli pøevést SAT, je také NP-úplné.
  85 Napøíklad nezávislá mno¾ina, rùzné varianty SATu, klika v~grafu~\dots
  86
  87 Jak taková tøída NP vypadá? Pøedstavme si v¹echny problémy tøídy NP, jakoby seøazené
  88 zhora dolu podle obtí¾nosti problémù (tedy navzdor gravitaci), kde porovnání dvou
  89 problémù urèuje pøevoditelnost (viz obrázek).
  90
  91 \figure{p-np.eps}{Struktura tøídy NP}{2.5cm}
  92
  93 Obecnì mohou nastat dvì situace, proto¾e nevíme, jestli ${\rm P}={\rm NP}$.
  94 Jestli ano, pak v¹echno je jedna a ta samá tøída. To by bylo v nìkterých
  95 pøípadech nepraktické, napø. ka¾dá ¹ifra by byla jednodu¹e rozlu¹titelná.
  96 \foot{Poznámka o ¹ifrách -- libovolnou funkci vyèíslitelnou v polynomiálním
  97 èase bychom umìli v polynomiálním èase také invertovat.}
  98 Jestli ne, NP-úplné problémy urèitì nele¾í v P, tak¾e P a NP-úplné problémy
  99 jsou dvì disjunktní èásti NP. Také se dá dokázat (to dìlat nebudeme, ale je
 100 dobré to vìdìt), ¾e je¹tì nìco le¾í mezi nimi, tedy ¾e existuje problém, který
 101 je v~NP, není v~P a není NP-úplný (dokonce je takových problémù nekoneènì mnoho,
 102 v nekoneènì tøídách).
 103
 104 \s{Katalog NP-úplných problémù}
 105
 106 Uká¾eme si nìkolik základních NP-úplných problémù. O~nìkterých jsme to dokázali
 107 na~minulé pøedná¹ce, o~dal¹ích si to doká¾eme nyní, zbylým se na~zoubek podíváme
 108 na~cvièeních.
 109
 110 \itemize\ibull
 111 \:{\I logické:}
 112   \itemize\ibull
 113     \:SAT (splnitelnost logických formulí v~CNF)
 114     \:3-SAT (ka¾dá klauzule obsahuje max.~3 literály)
 115     \:3,3-SAT (a navíc ka¾dá promìnná se vyskytuje nejvý¹e tøikrát)
 116     \:SAT pro obecné formule (nejen CNF)
 117     \:Obvodový SAT (není to formule, ale obvod)
 118   \endlist
 119 \:{\I grafové:}
 120   \itemize\ibull
 121     \:Nezávislá mno¾ina (existuje mno¾ina alespoò~$k$ vrcholù taková, ¾e ¾ádné dva nejsou propojeny hranou?)
 122     \:Klika (existuje úplný podgraf na~$k$ vrcholech?)
 123     \:3D párování (tøi mno¾iny se zadanými trojicemi, existuje taková mno¾ina disjunktních trojic, ve~které jsou v¹echny prvky?)
 124     \:Barvení grafu (lze obarvit vrcholy $k$~barvami tak, aby vrcholy stejné barvy nebyly nikdy spojeny hranou? NP-úplné u¾ pro~$k=3$)
 125     \:Hamiltonovská cesta (cesta obsahující v¹echny vrcholy [právì jednou])
 126     \:Hamiltonovská kru¾nice (kru¾nice, která nav¹tíví v¹echny vrcholy [právì jednou])
 127   \endlist
 128 \:{\I èíselné:}
 129   \itemize\ibull
 130     \:Batoh (nejjednodu¹¹í verze: dána mno¾ina èísel, zjistit, zda existuje podmno¾ina se zadaným souètem)
 131         \:Batoh -- optimalizace (podobnì jako u pøedchozího problému, ale místo mno¾iny èísel máme mno¾inu
 132                 pøedmìtù s vahami a cenami, chceme co nejdra¾¹í podmno¾inu její¾ váha nepøesáhne zadanou kapacitu
 133                 batohu)
 134     \:Loupe¾níci (lze rozdìlit danou mno¾inu èísel na~dvì podmno¾iny se stejným souètem)
 135     \:$Ax=b$ (soustava celoèíslených lineárních rovnic; $x_i$ mohou být pouze 0 nebo 1; NP-úplné i pokud $A_{ij}\in\{0,1\}$ a $b_i\in\{0,1\}$)
 136     \:Celoèíselné lineární programování (existuje vektor nezáporných celoèísených $x$ takový, ¾e $Ax \leq b$ ?)
 137   \endlist
 138 \endlist
 139
 140 Nyní si uká¾eme, jak pøevést SAT na nìjaký problém. Kdy¾ chceme ukázat, ¾e na
 141 nìco se dá pøevést SAT, potøebujeme obvykle dvì vìci:
 142 konstrukci, která bude simulovat promìnné, tedy nìco, co nabývá dvou stavù
 143 \<true>/\<false>; a nìco, co bude reprezentovat klauzule a umí zaøídit, aby
 144 ka¾dá klauzule byla splnìna alespoò jednou promìnnou.
 145 Roz¹iøme tedy ná¹ katalog problémù o následující:
 146 \h{3D párování (3D matching)}
 147
 148 \>{\I Vstup:} Tøi mno¾iny, napø. $K$ (kluci), $H$ (holky), $Z$ (zvíøátka) a
 149 mno¾ina $T$ kompatibilních trojic (tìch, kteøí se spolu snesou),
 150         tj. $T \subseteq K\times H\times Z$.
 151
 152 \>{\I Výstup:} Perfektní podmno¾ina trojic $P\subseteq K\times H \times Z$ --
 153         tj. taková podmno¾ina trojic, ¾e $(\forall k\in K\ \exists !p\in P: k\in p)
 154         \wedge(\forall h\in H\ \exists !p\in P: h\in p)
 155         \wedge(\forall z\in Z\ \exists !p\in P: z\in p)$ -- tedy ka¾dý byl vybrán
 156         právì jednou.
 157
 158
 159 \h{ Uká¾eme, jak na 3D-párování pøevést 3,3-SAT }
 160
 161 Uva¾ujme takovouto konfiguraci:
 162
 163 \fig{3d.eps}{4cm}
 164
 165 \>4 zvíøátka, 2 kluci, 2 dívky a 4 trojice, které oznaèíme $A, B, C, D$.
 166 Je¹tì pøedpokládáme, ¾e zvíøátka
 167  se mohou úèastnit nìjakých jiných trojic, ale
 168 tito ètyøi lidé se vyskytují pouze v~tìchto ètyøech trojicích a~nikde jinde.
 169 V¹imneme si, ¾e existují právì dvì mo¾nosti, jak tento obrázek spárovat.
 170 Abychom spárovali kluka $k_1$, tak si musíme vybrat $A$ nebo $B$. Kdy¾ si
 171 vybereme $A$, $k_1$ i $d_2$ u¾ jsou spárovaní tak¾e si nesmíme vybrat $B$ ani
 172 $D$. Pak jediná mo¾nost, jak spárovat $d_1$ a~$k_2$ je $C$. Jedna mo¾nost je
 173 tedy vybrat si $A$ a $C$ a jeliko¾ je obrázek symetrický, tak kdy¾ vybereme
 174 místo $A$ trojici $B$, dostaneme $B$ a~$D$. V¾dy si tedy vybereme dvì protìj¹í
 175 trojice v~obrázku.
 176
 177 Tyto konfigurace budeme pou¾ívat k~reprezentaci promìnných. Pro ka¾dou
 178 promìnnou si nakreslíme takový obrázek a~to, ¾e $A$ bude spárované s~$C$, bude
 179 odpovídat tomu, ¾e $x=1$, a~spárování $B$ a~$D$ bude odpovídat
 180  $x=0$. Pokud jsme
 181 pou¾ili $A$ a~$C$, zvíøata se sudými èísly, tj. $z_2$ a~$z_4$, horní a~dolní,
 182 jsou nespárovaná a~pokud jsme pou¾ili $B$ a~$D$, zvíøátka $z_1$ a~$z_3$ zùstala
 183 nespárovaná. Pøes tato nespárovaná zvíøátka mù¾eme pøedávat informaci, jestli
 184 promìnná $x$ má hodnotu \<true> nebo \<false> do dal¹ích èástí vstupu.
 185
 186 Zbývá vymyslet, jak reprezentovat klauzule. Klauzule jsou trojice popø. dvojice
 187 literálù, napø. $\kappa = (x \lor y \lor \lnot r)$, kde
 188 potøebujeme zajistit, aby $x$ bylo nastavené na $1$ nebo $y$ bylo nastavené
 189 na~$1$ nebo $r$ na $0$.
 190
 191 \fig{klauzule.eps}{4cm}
 192
 193 \>Pro takovouto klauzuli si poøídíme dvojici kluk-dívka, kteøí budou figurovat
 194 ve tøech trojicích se tøemi rùznými zvíøátky, co¾ mají být volná zvíøátka
 195 z~obrázkù pro pøíslu¹né promìnné (podle toho, má-li se promìnná vyskytnout
 196 s negací nebo ne). A~zaøídíme to tak, aby ka¾dé zvíøátko bylo
 197 pou¾ité maximálnì v~jedné takové trojici, co¾ jde proto, ¾e ka¾dý literál se
 198 vyskytuje maximálnì dvakrát a~pro ka¾dý literál máme dvì volná zvíøátka,
 199 z~èeho¾ plyne, ¾e zvíøátek je dost pro v¹echny klauzule. Pro dvojice se postupuje
 200 obdobnì.
 201
 202 Je¹tì nám ale urèitì zbude $2p-k$ zvíøátek, kde $p$ je poèet promìnných, $k$
 203 poèet klauzulí -- ka¾dá promìnná vyrobí 4 zvíøátka, klauzule zba¹tí jedno
 204 a samotné ohodnocení 2 zvíøátka -- tak pøidáme je¹tì $2p-k$ párù
 205 kluk-dìvèe, kteøí milují
 206 v¹echna zvíøátka, a~ti vytvoøí zbývající trojice.
 207
 208 Pokud formule byla splnitelná, pak ze splòujícího ohodnocení mù¾eme vyrobit
 209 párování s~na¹í konstrukcí. Obrázek pro ka¾dou promìnnou spárujeme podle
 210 ohodnocení, tj. promìnná je $0$ nebo $1$ a~pro ka¾dou klauzuli si vybereme
 211 nìkterou z~promìnných, kterými je ta klauzule splnìna. Funguje to ale
 212 i~opaènì: Kdy¾ nám nìkdo dá párovaní v~na¹í konstrukci, pak z nìho doká¾eme
 213 vyrobit splòující ohodnocení dané formule. Podíváme se, v~jakém stavu je
 214 promìnná, a~to je v¹echno. Z~toho, ¾e jsou správnì spárované klauzule, u¾
 215 okam¾itì víme, ¾e jsou v¹echny splnìné.
 216
 217 Zbývá ovìøit, ¾e na¹e redukce funguje v~polynomiálním èase. Pro ka¾dou klauzuli
 218 spotøebujeme konstantnì mnoho èasu, $2p-k$ je také polynomiálnì mnoho a~kdy¾ v¹e
 219 seèteme, máme polynomiální èas vzhledem k~velikosti vstupní formule. Tím je
 220 pøevod hotový a~mù¾eme 3D-párování zaøadit mezi NP-úplné problémy.
 221
 222
 223 %RK
 224
 225
 226 \h{Náznak dùkazu Cookovy vìty}
 227
 228 Abychom mohli budovat teorii NP-úplnosti, potøebujeme alespoò jeden problém,
 229 o kterém doká¾eme, ¾e je NP-úplný, z definice. Cookova vìta øíká o NP-úplnosti
 230 SAT-u, ale nám se to hodí dokázat o tro¹ku jiném problému -- {\I obvodovém SAT-u}.
 231
 232 \>{\I Obvodový SAT} je splnitelnost, která nepracuje s~formulemi, ale s~booleovskými
 233 obvody (hradlovými sítìmi). Ka¾dá formule se dá pøepsat do booleovského obvodu,
 234 který ji poèítá, tak¾e dává smysl zavést splnitelnost i pro obvody. Na¹e obvody
 235 budou mít nìjaké vstupy a~jenom jeden výstup. Budeme se ptát, jestli se vstupy
 236 tohoto obvodu dají nastavit tak, abychom na výstupu dostali \<true>.
 237
 238 \>Nejprve doká¾eme NP-úplnost {\I obvodového SAT-u} a~pak uká¾eme, ¾e se dá
 239 pøevést na obyèejný SAT v~CNF. Tím bude dùkaz Cookovy vìty hotový. Zaènìme
 240 s pomocným lemmatem.
 241
 242 \s{Lemma:} Nech» $L$ je problém v P. Potom existuje polynom $p$ a algoritmus,
 243 který pro $\forall n \ge 0$ spoète v èase $p(n)$ hradlovou sí» $Bn$ s $n$ vstupy
 244 a 1 výstupem takovou, ¾e $\forall x \in \{ 0, 1 \}^n : Bn(x) = L(x)$.
 245
 246 \proof
 247 Náznakem. Na základì zku¹eností z Principù poèítaèù intuitivnì chápeme poèítaèe
 248 jako nìjaké slo¾ité booleovské obvody, jejich¾ stav se mìní v~èase. Uva¾me tedy
 249 nìjaký problém $L \in {\rm P}$ a polynomiální algoritmus, který ho øe¹í. Pro vstup
 250 velikosti~$n$ dobìhne v~èase~$T$ polynomiálním v~$n$ a spotøebuje $\O(T)$ bunìk pamìti.
 251 Staèí nám tedy \uv{poèítaè s~pamìtí velkou $\O(T)$}, co¾ je nìjaký booleovský obvod
 252 velikosti polynomiální v~$T$, a~tedy i v~$n$. Vývoj v~èase o¹etøíme tak, ¾e sestrojíme~$T$
 253 kopií tohoto obvodu, ka¾dá z~nich bude odpovídat jednomu kroku výpoètu a bude
 254 propojena s~\uv{minulou} a \uv{budoucí} kopií. Tím sestrojíme booleovský obvod,
 255 který bude øe¹it problém~$L$ pro vstupy velikosti~$n$ a bude polynomiálnì velký
 256 vzhledem k~$n$.
 257
 258 \s{Poznámka:}
 259 Pro dùkaz následující vìty si dovolíme drobnou úpravu v~definici tøídy NP.
 260 Budeme chtít, aby nápovìda byla
 261 mìla pevnou velikost, závislou pouze na~velikosti vstupu (tedy: $\vert y \vert
 262 = g(\vert x \vert)$ namísto $\vert y \vert \le g(\vert x \vert)$). Proè je taková
 263 úprava BÚNO? Jistì si dovedete pøedstavit,
 264 ¾e pùvodní nápovìdu doplníme na po¾adovanou délku nìjakými \uv{mezerami}, které
 265 program ignoruje. (Tedy upravíme program tak, aby mu nevadilo, ¾e dostane na
 266 konci nápovìdy nìjak kódované mezery.)
 267
 268 \s{Vìta:} Obvodový SAT je NP-úplný.
 269
 270 \proof
 271 Máme tedy nìjaký problém $L$ z~NP a~chceme dokázat, ¾e $L$ se dá pøevést
 272 na~obvodový SAT (tj. NP-tì¾kost). Kdy¾ nám nìkdo pøedlo¾í nìjaký vstup $x$
 273 (chápeme jako posloupnost $x_1, x_2, \ldots, x_n$),
 274 spoèítáme velikost nápovìdy $g(n)$. Víme, ¾e kontrolní
 275 algoritmus~$K$ (který kontroluje, zda nápovìda je správnì) je v~P. Vyu¾ijeme
 276 pøedhozí lemma, abychom získali obvod, který pro konkrétní velikost vstupu
 277 $x$ poèítá to, co kontrolní algoritmus $K$. Na vstupu tohoto obvodu bude $x$
 278 (vstup problému $L$) a~nápovìda~$y$. Na výstupu nám øekne, jestli je nápovìda
 279 správná. Velikost vstupu tohoto obvodu bude tedy $p(g(n))$, co¾ je také polynom.
 280
 281 \fig{kobvod.eps}{2.3cm}
 282
 283 \>V tomto obvodu zafixujeme vstup $x$ (na místa vstupu dosadíme konkrétní hodnoty z $x$). Tím získáme obvod, jeho¾ vstup je jen $y$ a~ptáme se, zda za $y$ mù¾eme dosadit nìjaké hodnoty tak, aby na výstupu bylo \<true>. Jinými slovy, ptáme se, zda je tento obvod splnitelný.
 284
 285 \>Pro libovolný problém z~NP tak doká¾eme sestrojit funkci, která pro ka¾dý vstup~$x$ v~polynomiálním èase vytvoøí obvod, který je splnitelný pravì tehdy, kdy¾ odpovìï tohoto problému na vstup $x$ má být \<true>. Tedy libovolný problém z~NP se dá
 286 v~polynomiálním èase pøevést na obvodový SAT.
 287
 288 \>Obvodový SAT je v NP triviálnì - ??? staèí topologicky setøídit a pak brát hradla postupnì.???
 289 \qed
 290
 291 \s{Lemma:} Obvodový SAT se dá pøevést na 3-SAT.
 292
 293 \proof
 294 Budeme postupnì budovat formuli v~konjunktivní normální formì. Ka¾dý booleovský obvod se dá pøevést v~polynomiálním èase na~ekvivalentní obvod, ve~kterém se vyskytují jen hradla {\sc and} a {\sc not}, tak¾e staèí najít klauzule odpovídající tìmto hradlùm. Pro ka¾dé hradlo v~obvodu zavedeme novou promìnnou popisující jeho výstup. Pøidáme klauzule, které nám kontrolují, ¾e toto hradlo máme ohodnocené konzistentnì.
 295
 296 \>{\I Pøevod hradla \sc not}: na vstupu hradla budeme mít nìjakou promìnnou $x$ (která pøi¹la buïto pøímo ze~vstupu toho celého obvodu nebo je to promìnná, která vznikla na výstupu nìjakého hradla) a na výstupu promìnnou $y$. Pøidáme klauzule, které nám zaruèí, ¾e jedna promìnná bude negací té druhé:
 297 $$\matrix{ (x \lor y), \cr
 298   (\neg{x} \lor \neg{y}). \cr }
 299   \hskip 0.2\hsize
 300 \vcenter{\hbox{\epsfxsize=0.7cm\epsfbox{not.eps}}}
 301 $$
 302
 303 \>{\I Pøevod hradla \sc and}: Hradlo má vstupy $x, y$ a~výstup $z$. Potøebujeme pøidat klauzule, které nám popisují, jak se má hradlo {\sc and} chovat. Tyto vztahy pøepí¹eme do~konjunktivní normální formy:
 304 $$
 305 \left. \matrix{
 306   x\ \&\ y \Rightarrow z \cr
 307   \neg{x} \Rightarrow \neg{z} \cr
 308   \neg{y} \Rightarrow \neg{z} \cr
 309 }
 310 \ \quad
 311  \right\}
 312 \quad
 313 \matrix{
 314  (z \lor \neg{x} \lor \neg{y}) \cr
 315  (\neg{z} \lor x)              \cr
 316  (\neg{z} \lor y)              \cr
 317  }
 318  \hskip 0.1\hsize
 319 \vcenter{\hbox{\epsfxsize=0.7cm\epsfbox{and.eps}}}
 320 $$
 321
 322 \>Kdy¾ chceme pøevádìt obvodový SAT na 3-SAT, obvod nejdøíve pøelo¾íme na takový, ve~kterém jsou jen hradla {\sc and} a~{\sc not}, a~pak hradla tohoto obvodu pøelo¾íme na klauzule. Formule vzniklá z~takovýchto klauzulí je splnitelná pravì tehdy, kdy¾ je splnitelný daný obvod. Pøevod pracuje v polynomiálním èase.
 323 \qed
 324
 325 \s{Poznámka:}
 326 Kdy¾ jsme zavádìli SAT, omezili jsme se jen na formule, které jsou
 327 v~konjunktivní normální formì (CNF). Teï u¾ víme, ¾e splnitelnost obecné
 328 booleovské formule doká¾eme pøevést na obvodovou splnitelnost a tu pak
 329 pøevést na 3-SAT. Opaèný pøevod je samozøejmì triviální, tak¾e obecný SAT
 330 je ve~skuteènosti ekvivalentní s~na¹ím \uv{standardním} SATem pro CNF.
 331
 332 \bye
 333