From 3f63575cf1eaa5ddb92f52a201676aceb6cb9b09 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 21 Jan 2008 10:24:02 +0100 Subject: [PATCH] Spousta drobnych vylepseni formulaci. Rozsiren katalog NP-uplnych problemu. --- 11-np/11-np.tex | 155 ++++++++++++++++++++++++++++++++++-------------- 1 file changed, 110 insertions(+), 45 deletions(-) diff --git a/11-np/11-np.tex b/11-np/11-np.tex index 46b4bbf..5786b86 100644 --- a/11-np/11-np.tex +++ b/11-np/11-np.tex @@ -2,74 +2,117 @@ \prednaska{11}{NP-úplné problémy}{(zapsali F. Kaèmarik, R. Krivák, D. Remi¹)} -Dosud jsme zkoumali problémy, které se nás ptaly na to, jestli nìco existuje. Napøíklad: dostali jsme formuli a problém splnitelnosti se nás ptal, zda existuje ohodnocení promìnných takové, ¾e formule platí. Nebo v~pøípade nezávislých mno¾in jsme dostali graf a èíslo $k$ a ptali jsme se, jestli v~grafu existuje nezávislá mno¾ina, která je veliká alespoò $k$. Tyto otázky mìly spoleèné to, ¾e kdy¾ nám nìkdo zadal nìjaký objekt, umìli jsme efektivnì øíci, zda je to objekt, který hledáme. Napøíklad: pokud dostaneme ohodnocení promìnných logické formule, staèí jen dosadit a spoèítat, ¾e formule je \ nebo \. Zjistit, ¾e nìjaký objekt je ten, který hledáme, umíme efektivnì. Tì¾ké na tom je takový objekt najít. Co¾ vede k~definici obecných vyhledávacích problémù, kterým se øíká tøída problémù NP. Definujeme si ji poøádnì, ale nejdøíve zaèneme tro¹ièku jednodu¹¹í tøídou. +Dosud jsme zkoumali problémy, které se nás ptaly na to, jestli nìco existuje. Napøíklad jsme dostali formuli a problém splnitelnosti se nás ptal, zda existuje ohodnocení promìnných takové, ¾e formule platí. Nebo v~pøípade nezávislých mno¾in jsme dostali graf a èíslo $k$ a ptali jsme se, jestli v~grafu existuje nezávislá mno¾ina, která obsahuje alespoò~$k$ vrcholù. Tyto otázky mìly spoleèné to, ¾e kdy¾ nám nìkdo zadal nìjaký objekt, umìli jsme efektivnì øíci, zda je to objekt, který hledáme. Napøíklad pokud dostaneme ohodnocení promìnných logické formule, staèí jen dosadit a spoèítat, ¾e formule je \ nebo \. Zjistit, ¾e nìjaký objekt je ten, který hledáme, umíme efektivnì. Tì¾ké na tom je takový objekt najít. Co¾ vede k~definici obecných vyhledávacích problémù, kterým se øíká tøída problémù NP. Definujeme si ji poøádnì, ale nejdøíve zaèneme tro¹ièku jednodu¹¹í tøídou. -\s{Definice:} $P$ je {\I tøída rozhodovacích problémù}, které jsou øe¹itelné v~polynomiálním èase. Jinak øeèeno, problém +\s{Definice:} P je {\I tøída rozhodovacích problémù}, které jsou øe¹itelné v~polynomiálním èase. Jinak øeèeno, problém $L \in P \Leftrightarrow \exists $ polynom $f$ a~$\exists$ algoritmus $A$ takový, ¾e $\forall x: L(x)=A(x)$ a $A(x)$ dobìhne v~èase $\O(f(x))$. Tøída P odpovídá tomu, o èem jsme se shodli, ¾e umíme efektivnì øe¹it. Nadefinujme tedy tøídu NP: -\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 -$K\in\rm{P}$ a $\exists$ polynom $g$ takový, ¾e pro +\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 +$K\in{\rm P}$ a $\exists$ polynom $g$ takový, ¾e pro $\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$. -\s{Pozorování:} Splnitelnost logických formulí je v~NP. +\s{Pozorování:} Splnitelnost logických formulí je v~NP. Staèí si toti¾ nechat napovìdìt, jak +ohodnotit jednotlivé promìnné a pak ovìøit, jestli je formule splnìna. Nápovìda je polynomiálnì +velká (dokonce lineárnì), splnìní zkontrolujeme také v~lineárním èase. Odpovíme tedy ano právì +tehdy, existuje-li nápovìda, která nás pøesvìdèí, tedy pokud je formule splnitelná. -Máme-li lineárnì velké nápovìdy, co¾ jsou ohodnocení promìnných zadané formule, odpovíme ano, formule je splnitelná, pokud nám nìkdo mù¾e odpovìdìt na splòující ohodnocení. Tak¾e $K$ nám ovìøí, èi dosazením ohodnocení je formule splnìna a ptáme se tedy, èi existuje nápovìda taková, která odpovídá ohodnocení, v~nìm¾ je formule splnìna. Splnitelnost logických formulí je urèitì v~tøídì NP. - -\s{Pozorování:} Tøída $P$ le¾í uvnitø NP. +\s{Pozorování:} Tøída P le¾í uvnitø NP. V~podstatì øíkáme, ¾e kdy¾ máme problém, který umíme øe¹it v~polynomiálním èase bez nápovìdy, tak to zvládneme v~polynomiálním èase i s~nápovìdou. Nasbírali jsme problémy, které jsou v~NP, ale nevíme, jestli jsou v~P. Brzy uká¾eme, ¾e to jsou v jistém smyslu nejtì¾¹í problémy v~NP. Nadefinujme si: -\s{Definice:} Problém $L$ je NP-{\I tì¾ký} právì tehdy, kdy¾ je pøevoditelný: -$\forall M \in \rm{NP}: M~\rightarrow~L$. (Viz definici pøevodù z minulé pøedná¹ky) +\s{Definice:} Problém $L$ je NP-{\I tì¾ký} právì tehdy, kdy¾ je na~nìj pøevoditelný +ka¾dý problém z~NP. (Viz definici pøevodù z minulé pøedná¹ky) -Také platí, ¾e pokud umíme øe¹it nìjaký NP-tì¾ký problém v~polynomiálním èase, pak umíme vyøe¹it v~polynomiálním èase v¹e v~NP, pokud nìjaké takové~$\in~\rm{P} \Rightarrow \rm{P}=\rm{NP} $. +Také platí, ¾e pokud umíme øe¹it nìjaký NP-tì¾ký problém v~polynomiálním èase, +pak umíme vyøe¹it v~polynomiálním èase v¹e v~NP, a tedy ${\rm P}={\rm NP}$. +(To u¾ také víme z~minulé pøedná¹ky.) -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é. +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é. -\s{Definice:} Problém $L$ je NP-{\I úplný} právì tehdy, kdy¾ $L$ je NP-tì¾kýa $L \in \rm{NP}$. +\s{Definice:} Problém $L$ je NP-{\I úplný} právì tehdy, kdy¾ $L$ je NP-tì¾ký a $L \in {\rm NP}$. -NP-úplné problémy jsou ve své podstatì nejtì¾¹í problémy, které le¾í v~NP. Proto¾e NP-úplné problémy le¾í v~NP, umíme na nì pøevést libovolný problém z NP. Kdybychom umìli vyøe¹it nìjaký NP-úplný problém v~polynomiálním èase, pak v¹echno v~NP je øe¹itelné v~polynomiálním èase. Bohu¾el, to jestli nìjaký NP-úplný problém lze øe¹it v~polynomiálním se neví. Otázka, jestli $\rm{P}=\rm{NP}$ je asi nejznámìj¹í otevøený problém v~celé teoretické informatice. +NP-úplné problémy jsou tedy ve~své podstatì nejtì¾¹í problémy, které le¾í v~NP. +Kdybychom umìli vyøe¹it nìjaký NP-úplný problém v~polynomiálním èase, pak +v¹echno v~NP je øe¹itelné v~polynomiálním èase. Bohu¾el to, jestli nìjaký +NP-úplný problém lze øe¹it v~polynomiálním èase, se neví. Otázka, jestli +${\rm P}={\rm NP}$, je asi nejznámìj¹í otevøený problém v~celé teoretické +informatice. -Uká¾eme si nìjaký NP-úplný problém. Velmi se nám bude hodit následující vìta: +Kde ale nìjaký NP-úplný problém vzít? K~tomu se nám bude velice hodit následující vìta: \s{Vìta (Cookova):} SAT je NP-úplný. -\>Dùkaz je pøíli¹ technický, jenom ho pøibli¾nì naznaèíme pozdìji. Pøímým dùsledkem je, ¾e cokoli v~NP je pøevoditelné na SAT. +\>Dùkaz je znaènì technický, pøibli¾nì ho naznaèíme pozdìji. Pøímým dùsledkem je, ¾e cokoli v~NP je pøevoditelné na SAT. K dokazování NP-úplnosti dal¹ích problémù pou¾ijeme následující vìtièku: -\s{Vìtièka:} $L$ je NP-úplný a $L$ se dá pøevést na $M$ ($L \rightarrow M$), $M \in \rm{NP} \Rightarrow M$ je také NP-úplný. +\s{Vìtièka:} Pokud problém $L$ je NP-úplný a $L$ se dá pøevést na $M\in{\rm NP}$ ($L \rightarrow M$), pak $M$ je také NP-úplný. \proof -Tuto vìtièku staèí dokázat pro NP tì¾kost, NP-úplnost plyne okam¾itì z~toho, ¾e problémy jsou NP tì¾ké a le¾í v~NP, podle pøedpokladu. -Víme ¾e $L$ se dá pøevést na $M$. $L$ je NP-úplný,z~toho plyne, ¾e ka¾dý problém $Q$ z NP se dá pøevést na $L$. $Q$ se dá pøevést na $L$, $L$ se dá pøevést na $M$. Z~toho plyne, ¾e $Q$ se dá pøevést na $M$. Staèí tedy slo¾it funkci $f(Q \rightarrow L)$ s~funkcí $g(L \rightarrow M)$. To urèitì také spoèteme v~polynomiálním èase. Tak nahlédneme, ¾e v¹echny problémy z NP se dají pøevést na problém $M$. +Tuto vìtièku staèí dokázat pro NP-tì¾kost, NP-úplnost plyne okam¾itì z~toho, ¾e +problémy jsou NP-tì¾ké a le¾í v~NP (podle pøedpokladu). + +Víme, ¾e $L$ se dá pøevést na~$M$ nìjakou funkcí~$f$. Jeliko¾ $L$ je NP-úplný, +pak pro ka¾dý problém $Q\in{\rm NP}$ existuje nìjaká funkce~$g$, která pøevede +$Q$ na~$L$. Staèí tedy slo¾it funkci~$f$ s~funkcí~$g$, èím¾ získáme funkci pracující +opìt v~polynomiálním èase, která pøevede~$Q$ na~$M$. Ka¾dý problém z~NP se tedy +dá pøevést na problém~$M$. \qed -\s{Dùsledek:} Cokoliv, na co jsme umìli pøevést SAT, je také NP-úplné. Napøíklad nezávislá mno¾ina, v¹echny varianty SATu, klika v~grafu~\dots +\s{Dùsledek:} Cokoliv, na co jsme umìli pøevést SAT, je také NP-úplné. Napøíklad nezávislá mno¾ina, rùzné varianty SATu, klika v~grafu~\dots Jak taková tøída NP vypadá? Pøedstavme si v¹echny problémy tøídy NP, jakoby seøazené zhora nadolu podle obtí¾nosti problémù, kde porovnání dvou problémù urèuje pøevoditelnost (viz obrázek). \figure{p-np.eps}{Struktura tøídy NP}{2.5cm} -Obecnì mohou nastat dvì situace. Proto¾e nevíme, jestli $\rm{P}=\rm{NP}$. Jestli ano, pak v¹echno je jedna a ta samá tøída. To by bylo v nìkterých pøípadech nepraktické, napø. ka¾dá ¹ifra by byla jednodu¹e rozlu¹titelná. Jestli ne, NP-úplné problémy urèitì nele¾í v P, P a NP-úplné problémy jsou dvì disjunktní èásti NP. Taky se dá dokázat, ¾e je¹tì nìco le¾í mezi nimi. Existuje problém, který je v NP, není v P a není NP-úplný. To v¹ak dokazovat nebudeme. +Obecnì mohou nastat dvì situace. Proto¾e nevíme, jestli ${\rm P}={\rm NP}$. +Jestli ano, pak v¹echno je jedna a ta samá tøída. To by bylo v nìkterých +pøípadech nepraktické, napø. ka¾dá ¹ifra by byla jednodu¹e rozlu¹titelná. +Jestli ne, NP-úplné problémy urèitì nele¾í v P, tak¾e P a NP-úplné problémy +jsou dvì disjunktní èásti NP. Také se dá dokázat (to dìlat nebudeme, ale je +dobré to vìdìt), ¾e je¹tì nìco le¾í mezi nimi, tedy ¾e existuje problém, který +je v~NP, není v~P a není NP-úplný. -\s{Katalog NP-úplných problémù:} +\s{Katalog NP-úplných problémù} + +Uká¾eme si nìkolik základních NP-úplných problémù. O~nìkterých jsme to dokázali +na~minulé pøedná¹ce, o~dal¹ích si to doká¾eme nyní, zbylým se na~zoubek podíváme +na~cvièeních. + \itemize\ibull -\:{\I logické:} -SAT, 3-SAT, 3,3-SAT, obvodový SAT, SAT pro obecné formule (splnitelnosti logických formulí, viz pøedchozí pøedná¹ky) +\:{\I logické:} + \itemize\ibull + \:SAT (splnitelnost logických formulí v~CNF) + \:3-SAT (ka¾dá klauzule obsahuje max.~3 literály) + \:3,3-SAT (a navíc ka¾dá promìnná se vyskytuje nejvý¹e tøikrát) + \:SAT pro obecné formule (nejen CNF) + \:Obvodový SAT (není to formule, ale obvod) + \endlist \:{\I grafové:} -Maximální nezávislá mno¾ina (max. mno¾ina vrcholù, které nejsou propojené hranou), klika v~grafu (najít uplný podgraf v grafu), 3D párování (tøi mno¾iny, mno¾ina kompatibilních trojic, najít perfektnù mno¾inu vyhovujících trojíc), 3-barvení (obarvit graf 3 barvami tak, aby nebyli dvì stejné barvy vedle sebe), Hamiltonova cesta (cesta v grafu,obsahuje v¹echny vrcholy grafu, ka¾dý právì jednou), Hamiltonova kru¾nice (cyklus bez opakování vrcholù, obsahuje v¹echny vrcholy grafu, ka¾dý vrchol právì jednou) + \itemize\ibull + \:Nezávislá mno¾ina (mno¾ina alespoò~$k$ vrcholù taková, ¾e ¾ádné dva nejsou propojeny hranou) + \:Klika (úplný podgraf na~$k$ vrcholech) + \:3D párování (tøi mno¾iny se zadanými trojicemi, najít takovou mno¾inu disjunktních trojic, ve~které jsou v¹echny prvky) + \:Barvení grafu (obarvit vrcholy $k$~barvami tak, aby vrcholy stejné barvy nebyly nikdy spojeny hranou; NP-úplné u¾ pro~$k=3$) + \:Hamiltonovská cesta (cesta obsahující v¹echny vrcholy [právì jednou]) + \:Hamiltonovská kru¾nice (kru¾nice, která nav¹tíví v¹echny vrcholy [právì jednou]) + \endlist \:{\I èíselné:} -problém batohu (daná mno¾ina èísel, zjistit zda existuje podmno¾ina se zadaným souètem), loupe¾níci (rozdìlit mno¾inu na dvì podmno¾iny se stejným souètem), $Ax=b$ (soustava celoèíslených lineárních rovnic, x mohou být pouze 0 nebo 1, jinak v¹echno poèítame v celých èíslech), celoèíselné lineární programování (existuje vektor platných nezáporných celoèísených $x$, ¾e platí $Ax \leq b$) + \itemize\ibull + \:Batoh (nejjednodu¹¹í verze: dána mno¾ina èísel, zjistit, zda existuje podmno¾ina se zadaným souètem) + \:Loupe¾níci (rozdìlit mno¾inu na~dvì podmno¾iny se stejným souètem) + \:$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\}$) + \:Celoèíselné lineární programování (existuje vektor nezáporných celoèísených $x$ takový, ¾e $Ax \leq b$) + \endlist \endlist \h { Pøevoditelnost 3,3-SAT na 3D-párování } 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ù \/\, a nìco, co bude reprezentovat klauzule a umí zaøídit, aby ka¾dá klauzule byla splnìna alespoò jednou promìnnou. -Jenom pro pøipomenutí, máme mno¾inu klukù, dìvèat, zvíøátek a nìjaké trojice, kdo se s~kým snese a chceme vybrat trojice tak, aby se v~nich ka¾dý kluk, holka, zvíøátko vyskytovalo právì jednou. +Jenom pro pøipomenutí, máme mno¾inu klukù, dìvèat, zvíøátek a nìjaké trojice, kdo se s~kým snese, a chceme vybrat trojice tak, aby se v~nich ka¾dý kluk, holka, zvíøátko vyskytovalo právì jednou. Najdeme si takovouto konfiguraci: \fig{3d.eps}{4cm} @@ -101,26 +144,45 @@ Zb Abychom mohli budovat teorii NP-úplnosti, potøebujeme alespoò jeden problém, o kterém doká¾eme, ¾e je NP-úplný, z definice. Cookova vìta øíká o NP-úplnosti SAT-u, ale nám se to hodí dokázat o tro¹ku jiném problému -- {\I obvodovém SAT-u}. -\>{\I Obvodový SAT} je splnitelnost, která nepracuje s~formulemi, ale s~booleovskými obvody. Ka¾dá formule se dá pøepsat do booleovského obvodu, který ji poèítá, tak¾e dává smysl zavést splnitelnost pro obvody. Na¹e obvody budou mít nìjaké vstupy a~jenom jeden výstup. Budeme se ptát, jestli se vstupy tohoto obvodu dají nastavit tak, abychom na výstupu dostali \. +\>{\I Obvodový SAT} je splnitelnost, která nepracuje s~formulemi, ale s~booleovskými obvody. Ka¾dá formule se dá pøepsat do booleovského obvodu, který ji poèítá, tak¾e dává smysl zavést splnitelnost i pro obvody. Na¹e obvody budou mít nìjaké vstupy a~jenom jeden výstup. Budeme se ptát, jestli se vstupy tohoto obvodu dají nastavit tak, abychom na výstupu dostali \. -\>Nejprve doká¾eme NP-úplnost {\I obvodového SAT-u} a~pak uká¾eme, ¾e se dá pøevést na formulový SAT. Tím bude dùkaz Cookovy vìty hotový. +\>Nejprve doká¾eme NP-úplnost {\I obvodového SAT-u} a~pak uká¾eme, ¾e se dá pøevést na obyèejný SAT v~CNF. Tím bude dùkaz Cookovy vìty hotový. \s{Vìta:} Obvodový SAT je NP-úplný. \proof -Náznakem. Na základì zku¹eností z Principù poèítaèù intuitivnì chápeme, ¾e pokud nìjaký problém $L \in \rm{P}$, pak existuje polynomiálnì velký booleovský obvod, který poèítá $L$. - -\>Dovolíme si drobnou úpravu v~definici tøídy NP. Budeme chtít, aby nápovìda byla pravì tak velká jako velikost vstupu (tedy: $\vert y \vert = g(\vert x \vert)$). Proè je taková úprava BÚNO? Jistì si dovedete pøedstavit, ¾e pùvodní nápovìdu doplníme -na po¾adovanou délku nìjakými \uv{mezerami}, které program ignoruje. (Tedy upravíme program tak, aby mu nevadilo, ¾e dostane na konci nápovìdy nìjak kódované mezery.) - -\>Máme nìjaký problém $L$ z~NP a~chceme dokázat, ¾e $L$ se dá pøevést na obvodový SAT. Kdy¾ nám nìkdo pøedlo¾í nìjaký vstup $x$ (chápeme jako vektor $(x_1, x_2, \dots)$), spoèítáme velikost nápovìdy $g(\vert x\vert)$. Víme, ¾e kontrolní algoritmus $K$ (který kontroluje, zda nápovìda je správnì) je v~P. Vyu¾ijeme intuice o~obvodech, abychom získali obvod, který pro konkrétní velikost vstupu $x$ poèítá to, co kontrolní algoritmus $K$. Na vstupu tohoto obvodu bude $x$ (vstup problému $L$) a~nápovìda $y$. -Na výstupu nám øekne, jestli je to nápovìda, která k~tomu patøí nebo nepatøí. Velikost vstupu tohoto obvodu bude tedy $\vert x\vert + g(\vert x\vert)$, co¾ je polynom. +Náznakem. Na základì zku¹eností z Principù poèítaèù intuitivnì chápeme poèítaèe +jako nìjaké slo¾ité booleovské obvody, jejich¾ stav se mìní v~èase. Uva¾me nìjaký +problém $L \in {\rm P}$ a polynomiální algoritmus, který ho øe¹í. Pro vstup velikosti~$n$ +tedy dobìhne v~èase~$T$ polynomiálním v~$n$ a spotøebuje $\O(T)$ bunìk pamìti. +Staèí nám tedy \uv{poèítaè s~pamìtí velkou $\O(T)$}, co¾ je nìjaký booleovský obvod +velikosti polynomiální v~$T$, a~tedy i v~$n$. Vývoj v~èase o¹etøíme tak, ¾e sestrojíme~$T$ +kopií tohoto obvodu, ka¾dá z~nich bude odpovídat jednomu kroku výpoètu a bude +propojena s~\uv{minulou} a \uv{budoucí} kopií. Tím sestrojíme booleovský obvod, +který bude øe¹it problém~$L$ pro vstupy velikosti~$n$ a bude polynomiálnì velký +vzhledem k~$n$. + +Je¹tì si dovolíme drobnou úpravu v~definici tøídy NP. Budeme chtít, aby nápovìda byla +mìla pevnou velikost, závislou pouze na~velikosti vstupu (tedy: $\vert y \vert += g(\vert x \vert)$). Proè je taková úprava BÚNO? Jistì si dovedete pøedstavit, +¾e pùvodní nápovìdu doplníme na po¾adovanou délku nìjakými \uv{mezerami}, které +program ignoruje. (Tedy upravíme program tak, aby mu nevadilo, ¾e dostane na +konci nápovìdy nìjak kódované mezery.) + +Máme tedy nìjaký problém $L$ z~NP a~chceme dokázat, ¾e $L$ se dá pøevést na obvodový +SAT. Kdy¾ nám nìkdo pøedlo¾í nìjaký vstup $x$ (chápeme jako vektor $(x_1, x_2, \ldots, x_n)$), +spoèítáme velikost nápovìdy $g(\vert x\vert)$. Víme, ¾e kontrolní +algoritmus~$K$ (který kontroluje, zda nápovìda je správnì) je v~P. Vyu¾ijeme +intuice o~obvodech, abychom získali obvod, který pro konkrétní velikost vstupu +$x$ poèítá to, co kontrolní algoritmus $K$. Na vstupu tohoto obvodu bude $x$ +(vstup problému $L$) a~nápovìda~$y$. Na výstupu nám øekne, jestli je nápovìda +správná. Velikost vstupu tohoto obvodu bude tedy $\vert x\vert + g(\vert x\vert)$, co¾ je polynom. \fig{kobvod.eps}{2.3cm} \>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 \. Jinými slovy, ptáme se, zda je tento obvod splnitelný. -\>Pro libovolný problém z~NP tak doká¾eme vyrobit 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 \. Tedy libovolný problém z~NP se dá +\>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 \. Tedy libovolný problém z~NP se dá v~polynomiálním èase pøevést na obvodový SAT. \qed @@ -131,8 +193,10 @@ Budeme postupn \>{\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é: $$\matrix{ (x \lor y), \cr - (\neg{x} \lor \neg{y}). \cr }$$ -\fig{not.eps}{0.8cm} + (\neg{x} \lor \neg{y}). \cr } + \hskip 0.2\hsize +\vcenter{\hbox{\epsfxsize=0.7cm\epsfbox{not.eps}}} +$$ \>{\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: $$ @@ -148,19 +212,20 @@ $$ (z \lor \neg{x} \lor \neg{y}) \cr (\neg{z} \lor x) \cr (\neg{z} \lor y) \cr - } $$ -\fig{and.eps}{0.9cm} + } + \hskip 0.1\hsize +\vcenter{\hbox{\epsfxsize=0.7cm\epsfbox{and.eps}}} +$$ -\>Kdy¾ chceme pøevádìt obvodový SAT na 3-SAT, obvod nejdøíve pøelo¾íme na takový, v~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. +\>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. \qed \s{Poznámka:} Kdy¾ jsme zavádìli SAT, omezili jsme se jen na formule, které jsou v~konjunktivní normální formì (CNF). Teï u¾ víme, ¾e splnitelnost obecné booleovské formule doká¾eme pøevést na obvodovou splnitelnost a tu pak -pøevést na 3-SAT. SAT bychom si tedy mohli definovat i jako problém -splnitelnosti obecných booleovských formulí. - +pøevést na 3-SAT. Opaèný pøevod je samozøejmì triviální, tak¾e obecný SAT +je ve~skuteènosti ekvivalentní s~na¹ím \uv{standardním} SATem pro CNF. \bye -- 2.39.2