\input lecnotes.tex
-\prednaska{11}{NP-úplné problémy}{(zapsali F. Kaèmarik, R. Krivák, D. Remi¹)}
+\prednaska{11}{NP-úplné problémy}{\vbox{\hbox{(zapsali F. Kaèmarik, R. Krivák, D. Remi¹}
+ \hbox{ Michal Kozák, Vojta Tùma)}}}
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 \<true> nebo \<false>. 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{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.
+Problémy z minulé pøedná¹ky jsou v¹echny v NP (napø. pro nezávislou
+mno¾inu je onou nápovìdou pøímo mno¾ina vrcholù deklarující nezávislost),
+o jejich pøíslu¹nosti do P ale nevíme nic.
+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 na~nìj pøevoditelný
-ka¾dý problém z~NP. (Viz definici pøevodù z minulé pøedná¹ky)
+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, 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é.
\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).
+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ù (tedy navzdor gravitaci), 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}$.
+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ý.
+je v~NP, není v~P a není NP-úplný (dokonce je takových problémù nekoneènì mnoho,
+v nekoneènì tøídách).
\s{Katalog NP-úplných problémù}
\:{\I èíselné:}
\itemize\ibull
\:Batoh (nejjednodu¹¹í verze: dána mno¾ina èísel, zjistit, zda existuje podmno¾ina se zadaným souètem)
+ \:Batoh -- optimalizace (podobnì jako u pøedchozího problému, ale místo mno¾iny èísel máme mno¾inu
+ pøedmìtù s váhami a cenami, chceme co nejdra¾¹í podmno¾inu její¾ váha nepøesáhne zadanou kapacitu
+ batohu)
\: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ù \<true>/\<false>, 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.
-Najdeme si takovouto konfiguraci:
+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.
+\h{3D párování (3D matching)}
-\fig{3d.eps}{4cm}
+\>{\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$.
-\>4 zvíøátka, 2 kluci, 2 dívky a~takové 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.
+\>{\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.
-Takovýto obrázek 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$ odpovídá $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 tyto nespárovaná zvíøátka mù¾eme pøedávat informaci, jestli promìnná $x$ má hodnotu \<true> nebo \<false> do dal¹ích èástí grafu.
-Zbývá vymyslet, jak reprezentovat klauzule. Klauzule budou vypadat jako trojice literálù:
-$\kappa = (x \lor y \lor \lnot r) $
-Potøebujeme zajistit, aby $x$ bylo nastavené na $1$ nebo $y$ bylo nastavené na $1$ nebo $r$ na $0$.
+\h { Pøevoditelnost 3,3-SAT na 3D-párování }
-\fig{klauzule.eps}{4cm}
+Najdeme si takovouto konfiguraci:
-\>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é. 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.
+\fig{3d.eps}{4cm}
-Je¹tì nám ale urèitì zbude $2p-k$ zvíøátek, kde $p$ je poèet promìnných, 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í páry.
+\>4 zvíøátka, 2 kluci, 2 dívky a~takové 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.
+
+Takovýto obrázek 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$ odpovídá $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 tyto nespárovaná zvíøátka mù¾eme pøedávat informaci, jestli
+promìnná $x$ má hodnotu \<true> nebo \<false> do dal¹ích èástí grafu.
+
+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$.
-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 také 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é.
+\fig{klauzule.eps}{4cm}
-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¾ to 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.
+\>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í páry.
+
+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 také 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¾ to
+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.
%RK
\>{\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 \<true>.
-\>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ý.
+\>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ý. Zaènìme s pomocným lemmatem.
-\s{Vìta:} Obvodový SAT je NP-úplný.
+\s{Lemma:} Nech» $L$ je problém v $P$. Potom existuje polynom $p$ a algoritmus, který pro $\forall n \ge 0$ spoète v èase $p(n)$ hradlovou sí» $B_n$ s $n$ vstupy a 1 výstupem takovou, ¾e $\forall x \in \{ 0, 1 \}^{n} : B_n(x) = L(x).$
\proof
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.
+jako nìjaké slo¾ité booleovské obvody, jejich¾ stav se mìní v~èase. Uva¾me tedy nìjaký
+problém $L \in {\rm P}$ a polynomiální algoritmus, který ho øe¹í. Pro vstup velikosti~$n$ 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
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
+\s{Poznámka:}
+Je¹tì si dovolíme drobnou úpravu v~definici tøídy NP. Budeme chtít, aby nápovìda
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.)
+program ignoruje (tedy upravíme program tak, aby mu nevadilo, ¾e dostane na
+konci nápovìdy nìjak kódované mezery).
+
+\s{Vìta:} Obvodový SAT je NP-úplný.
+\proof
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)$),
+SAT (tj. NP-tì¾kost). 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
\>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á
v~polynomiálním èase pøevést na obvodový SAT.
+
+\>Obvodový SAT je v NP triviálnì -- za nápovìdu staèí vzít ohodnocení vstupù, hradla topologicky setøídit a postupnì vyhodnocovat.
\qed
\s{Lemma:} Obvodový SAT se dá pøevést na 3-SAT.
je ve~skuteènosti ekvivalentní s~na¹ím \uv{standardním} SATem pro CNF.
\bye
-
projects / ads2.git / blobdiff