3 \prednaska{8}{Pøevody problémù a NP-úplnost}{}
5 \>Na této pøedná¹ce se budeme zabývat rozhodovacími problémy a jejich obtí¾ností.
6 Za jednoduché budeme trochu zjednodu¹enì pova¾ovat ty problémy, na~nì¾ známe algoritmus
7 pracující v~polynomiálním èase.
9 \s{Definice:} {\I Rozhodovací problém} je takový problém, jeho¾ výstupem je v¾dy {\csc ano}, nebo {\csc ne}.
10 [Formálnì bychom se na~nìj mohli dívat jako na~mno¾inu $L$ vstupù, na~které je odpovìï {\csc ano},
11 a místo $L(x)=\hbox{\csc ano}$ psát prostì $x\in L$.]
13 Vstupy mìjme zakódované jen pomocí nul a jednièek (obecnì je jedno, jaký základ pro soustavu
14 kódování zvolíme, pøevody mezi soustavami o nìjakém základu $\neq$ 1 jsou co do velikosti
15 zápisu polynomiální). Rozhodovací problém je tedy
16 $f:\ \{0,1\}^{\ast} \to \{0,1\}$, to jest funkce z mno¾iny v¹ech øetìzcù jednièek a nul
17 do mno¾iny $\{1,0\}$, kde 1 na výstupu znamená {\csc ano}, 0 {\csc ne}.
19 \s{Pøíklad:} Je dán bipartitní graf $G$ a $k \in {\bb N}$. Existuje v $G$
20 párování, které obsahuje alespoò $k$ hran?
22 To, co bychom ve~vìt¹inì pøípadù chtìli, je samozøejmì nejen zjistit, zda takové párování
23 existuje, ale také nìjaké konkrétní najít. V¹imnìme si ale, ¾e kdy¾ umíme rozhodovat
24 existenci párování v~polynomiálním èase, mù¾eme ho polynomiálnì rychle i najít:
26 Mìjme èernou skøíòku (fungující v polynomiálním èase), která odpoví, zda daný
27 graf má nebo nemá párování o~$k$ hranách. Odebereme z~grafu libovolnou hranu
28 a zeptáme se, jestli i tento nový graf má párovaní velikosti~$k$. Kdy¾ má, pak tato
29 hrana nebyla pro existenci párování potøebná, a~tak ji odstraníme. Kdy¾ naopak
30 nemá (hrana patøí do ka¾dého párování po¾adované velikosti), tak si danou hranu
31 poznamenáme a odebereme nejen ji a její vrcholy, ale také hrany, které do tìchto
32 vrcholù vedly. Toto je korektní krok, proto¾e v pùvodním grafu tyto vrcholy
33 byly navzájem spárované, a tedy nemohou být spárované s~¾ádnými jinými vrcholy.
34 Na~nový graf aplikujeme znovu tentý¾ postup. Výsledkem je mno¾ina hran, které patøí
35 do hledaného párování. Hran, a tedy i iterací na¹eho algoritmu, je polynomiálnì
36 mnoho a skøíòka funguje v polynomiálním èase, tak¾e celý algoritmus je polynomiální.
38 A~jak ná¹ rozhodovací problém øe¹it? Nejsnáze tak, ¾e ho pøevedeme
39 na~{jiný,\footnote{${}^{\dag}$}{vìrni matfyzáckým vtipùm}} který
40 u¾ vyøe¹it umíme. Tento postup jsme (právì u~hledání párování) u¾ pou¾ili
41 v~kapitole o~Dinicovì algoritmu. Vytvoøili jsme vhodnou sí», pro kterou
42 platilo, ¾e v~ní existuje tok velikosti~$k$ právì tehdy, kdy¾
43 v~pùvodním grafu existuje párování velikosti~$k$.
45 Takovéto pøevody mezi problémy mù¾eme definovat obecnì:
47 \s{Definice:} Jsou-li $A$, $B$ rozhodovací problémy, pak øíkáme, ¾e $A$ lze {\I
48 redukovat} (neboli {\it pøevést}) na $B$ (pí¹eme $A \rightarrow B$) právì tehdy,
49 kdy¾ existuje funkce $f$ spoèitatelná v polynomiálním èase taková, ¾e pro $\forall
50 x: A(x) = B(f(x))$. V¹imnìme si, ¾e $f$ pracující v polynomiálním èase vstup
51 zvìt¹í nejvíce polynomiálnì.
53 \s{Pozorování:} $A\rightarrow B$ také znamená, ¾e problém~$B$ je alespoò tak tì¾ký
54 jako problém~$A$ (tím myslíme, ¾e pokud lze $B$ øe¹it v~polynomiálním èase,
55 lze tak øe¹it i~$A$): Nech» problém~$B$ umíme øe¹it v~èase $\O(b^k)$, kde
56 $b$ je délka jeho vstupu. Nech» dále funkce $f$ pøevádìjící $A$ na $B$ pracuje
57 v~èase $\O(a^\ell)$ pro vstup délky~$a$. Spustíme-li tedy $B(f(x))$ na~nìjaký
58 vstup~$x$ problému~$A$, bude mít $f(x)$ délku $\O(a^\ell)$, kde $a=|q|$; tak¾e
59 $B(f(x))$ pobì¾í v~èase $\O(a^\ell + (a^\ell)^k) = \O(a^{k\ell})$, co¾ je
60 polynomiální v~délce vstupu~$a$.
63 \s{Pozorování:} Pøevoditelnost je
65 \:reflexivní (úlohu mù¾eme pøevést na tu stejnou identickým zobrazením): $A \rightarrow A$,
66 \:tranzitivní: Je-li $A \rightarrow B$ funkcí $f$, $B \rightarrow C$ funkcí $g$,
67 pak $A \rightarrow C$ slo¾enou funkcí $g \circ f$
68 (slo¾ení dvou polynomiálních funkcí je zase polynomiální funkce, jak u¾ jsme zpozorovali
69 v~pøedchozím odstavci).
71 \>Takovýmto relacím øíkáme kvaziuspoøádání -- nesplòují obecnì antisymetrii, tedy mù¾e nastat
72 $A\rightarrow B$ a $B\rightarrow A$. Omezíme-li se v¹ak na tøídy navzájem pøevoditelných
73 problémù, dostáváme ji¾ (èásteèné) uspoøádání. Existují i navzájem nepøevoditelné problémy --
74 napøíklad problém v¾dy odpovídající 1 a problém v¾dy odpovídající 0.
75 Nyní se ji¾ podíváme na nìjaké zajímavé problémy. Obecnì to budou problémy, na které
76 polynomiální algoritmus není znám, a vzájemnými pøevody zjistíme ¾e jsou stejnì tì¾ké.
79 \>Splnitelnost (satisfiability) logických formulí, tj. dosazení 1 èi
80 0 za promìnné v logické formuli tak, aby formule dala výsledek 1.
82 \>Zamìøíme se na speciální formu zadání formulí, {\I konjunktivní normální formu} (CNF),
83 které splòují následující podmínky:
85 \:{\I formule} je zadána pomocí {\I klauzulí}\footnote{${}^{\dag}$}{bez politických konotací} oddìlených $\land$,
86 \:ka¾dá {\I klauzule} je slo¾ená z {\I literálù} oddìlených $\lor$,
87 \:ka¾dý {\I literál} je buïto promìnná nebo její negace.
89 \>Formule mají tedy tvar:
90 $$\psi = (\ldots\lor\ldots\lor\ldots\lor\ldots) \land (\ldots\lor\ldots\lor\ldots\lor\ldots) \land \ldots $$
92 \>{\I Vstup:} Formule $\psi$ v konjunktivní normální formì.
94 \>{\I Výstup:} $\exists$ dosazení 1 a 0 za promìnné takové, ¾e hodnota formule $\psi(\ldots) = 1$.
98 \>Pøevod nìjaké obecné formule $\psi$ na jí ekvivalentní $\chi$ v~CNF mù¾e
99 zpùsobit, ¾e $\chi$ je exponenciálnì velká vùèi $\psi$.
100 Pozdìji uká¾eme, ¾e lze podniknout pøevod na takovou formuli $\chi'$ v~CNF, která sice není
101 ekvivalentní s $\psi$ (pøibydou nám promìnné, a ne ka¾dý roz¹íøený model
102 $\psi$ je modelem $\chi'$), ale je splnitelná právì tehdy, kdy¾ je splnitelná $\psi$ -- co¾ nám
103 pøesnì staèí -- a je lineárnì velká vùèi $\psi$.
105 \h{2. problém: 3-SAT}
106 \s{Definice:} 3-SAT je takový SAT, v nìm¾ ka¾dá klauzule obsahuje nejvý¹e tøi literály.
108 \s{Pøevod 3-SAT na SAT:}
109 Vstup není potøeba nijak upravovat, 3-SAT splòuje vlastnosti SATu, proto 3-SAT
110 $\rightarrow$ SAT (SAT je alespoò tak tì¾ký jako 3-SAT)
112 \s {Pøevod SAT na 3-SAT:}
113 Musíme formuli pøevést tak, abychom neporu¹ili splnitelnost.
115 \>Trik pro dlouhé klauzule: Ka¾dou \uv{¹patnou} klauzuli
116 $$(\alpha \lor \beta) \hbox{, t¾. } \vert\alpha\vert + \vert\beta\vert \ge 4
117 ,\ \vert\alpha\vert \geq 2,\ \vert\beta\vert\geq 2$$
118 pøepí¹eme na: $$(\alpha \lor x) \land (\beta \lor \lnot x),$$
119 kde $x$ je nová promìnná (pøi ka¾dém dìlení klauzule {\it jiná}
121 %kterou nastavíme tak, abychom neovlivnili splnitelnost formule.
123 \>Tento trik opakujeme tak dlouho, dokud je to tøeba -- formuli délky $k+l$
124 roztrhneme na formule délky $k+1$ a $l+1$. Pokud klauzule pùlíme, dostaneme
125 polynomiální èas (strom rekurze má logaritmicky pater -- formule délky alespoò 6
126 se nám pøi rozdìlení zmen¹í na dvì instance velikosti maximálnì $2/3$ pùvodní, krat¹í
127 formule nás netrápí; na ka¾dém patøe se vykoná tolik co na pøedchozím + $2^{hloubka}$
128 za pøidané formule). Velikost výsledné formule je tím pádem polynomiální vùèi pùvodní:
129 v ka¾dém kroku se pøidají jen dva literály, tedy celkem {\it èas na pøevod}$\cdot
134 \:$\alpha \Rightarrow$ zvolíme $x = 0$ (zajistí splnìní druhé poloviny nové formule),
135 \:$\beta \Rightarrow$ zvolíme $x = 1$ (zajistí splnìní první poloviny nové formule),
136 \:$\alpha ,\beta / \lnot\alpha ,\lnot\beta \Rightarrow$ zvolíme $x = 0/1$ (je nám to
137 jedno, celkové øe¹ení nám to neovlivní).
140 Nabízí se otázka, proè mù¾eme pøidanou promìnnou $x$ nastavovat, jak se nám zlíbí.
141 Vysvìtlení je prosté -- promìnná $x$ nám pùvodní formuli nijak neovlivní, proto¾e
142 se v ní nevyskytuje, proto ji mù¾eme nastavit tak, jak chceme.
144 \s{Poznámka:} U~3-SAT lze vynutit právì tøi literály, pro krátké klauzule
145 pou¾ijeme stejný trik:
146 $$(\alpha) \rightarrow (\alpha \vee \alpha) \rightarrow (\alpha \lor x) \land (\alpha \lor \lnot x).$$
148 \h{3. problém: Hledání nezávislé mno¾iny v grafu}
150 \>Existuje nezávislá mno¾ina vrcholù z~$G$ velikosti alespoò $k$?
152 \s{Definice:} {\I Nezávislá mno¾ina} (NzMna) budeme øíkat ka¾dé mno¾inì vrcholù grafu
153 takové, ¾e mezi nimi nevede ¾ádná hrana.
155 \figure{nezmna.eps}{Pøíklad nezávislé mno¾iny}{1in}
157 \>{\I Vstup:} Neorientovaný graf $G$, $k \in {\bb N}$.
159 \>{\I Výstup:} $\exists A \subseteq V(G)$, $\vert A \vert \ge k$: $\forall u,v \in A \Rightarrow uv \not\in E(G)$?
161 \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.
163 \>Uká¾eme, jak na~tento probém pøevést 3-SAT.
165 \s{Pøevod 3-SAT na NzMna:} Z ka¾dé klauzule vybereme jeden literál, jeho¾ nastavením se klauzuli
166 rozhodneme splnit. Samozøejmì tak, abychom v~rùzných klauzulích nevybírali
167 konfliktnì, tj.~$x$ a~$\lnot x$.
170 $(x \lor y \lor z) \land (x \lor \lnot y \lor \lnot z) \land (\lnot x \lor \lnot y \lor p) $.
172 \>Pro ka¾dou klauzuli sestrojíme graf (trojúhelník) a pøidáme \uv{konfliktní}
173 hrany, tj. $x$ a $\lnot x$. Poèet vrcholù grafu odpovídá poètu literálù ve formuli,
174 poèet hran je maximálnì kvadratický a pøevod je tedy polynomiální.
176 Existuje-li v grafu nezávislá mno¾ina velikosti $k$, pak z~ka¾dého z~$k$ trojúhelníkù
177 vybere právì jeden vrchol, a pøitom ¾ádné dva vrcholy nebudou odpovídat literálu a
178 jeho negaci -- tedy dostaneme ohodnocení promìnných splòujících alespoò $k$ klauzulí.
179 Na druhou stranu, existuje-li ohodnocení $k$ klauzulí, pak pøímo odpovídá nezávislé
180 mno¾inì velikosti $k$ (v ka¾dém trojúhelníku zvolíme právì jednu z ohodnocených
181 promìnných, nemù¾e se stát ¾e zvolíme vrcholy konfliktní hrany). Ptáme-li se tedy
182 na nezávislou mno¾inu velikosti odpovídající
183 poètu klauzulí, dostaneme odpovìï {\csc ano} právì tehdy, kdy¾ je formule splnitelná.
185 Jsou-li ve formuli i klauzule krat¹í ne¾ 3, mù¾eme je buïto prodlou¾it metodou vý¹e
186 popsanou; nebo si v grafu necháme dvoj- a jedno-úhelníky, které ¾ádné z na¹ich úvah
189 \figure{nezmna_graf.eps}{Ukázka pøevodu 3-SAT na nezávislou mno¾inu}{3in}
191 \s{Pøevod NzMna na SAT:}
194 \:Poøídíme si promìnné $v_1, \ldots, v_n$ odpovídající vrcholùm grafu. Promìnná $v_i$ bude
195 indikovat, zda se $i$-tý vrchol vyskytuje v~nezávislé mno¾inì (tedy pøíslu¹né ohodnocení
196 promìnných bude vlastnì charakteristická funkce nezávislé mno¾iny).
197 \:Pro ka¾dou hranu $ij \in E(G)$ pøidáme klauzuli $(\lnot v_i \lor \lnot v_j)$. Tyto klauzule
198 nám ohlídají, ¾e vybraná mno¾ina je vskutku nezávislá.
199 \:Je¹tì potøebujeme zkontrolovat, ¾e je mno¾ina dostateènì velká, tak¾e si její prvky
200 oèíslujeme èísly od~1 do~$k$. Oèíslování popí¹eme maticí promìnných $x_{ij}$, pøièem¾
201 $x_{ij}$ bude pravdivá právì tehdy, kdy¾ v~poøadí $i$-tý prvek nezávislé mno¾iny je vrchol~$v_j$
202 -- pøidáme tedy klauzule, které nám øeknou, ¾e vybrané do nezávislé mno¾iny jsou právì
203 ty vrcholy, které jsou touto maticí oèíslované: $\forall i,j$, $x_{ij} \Rightarrow v_j$
204 (jen dodejme, ¾e $a\Rightarrow b$ je definované jako $\neg a\vee b$).
205 \:Je¹tì potøebujeme zajistit, aby byla v~ka¾dém øádku i sloupci nejvý¹e jedna jednièka:
206 $\forall j,i,i^{'}, i\ne i^{'} : x_{ij} \Rightarrow \lnot x_{i^{'}j}$ a
207 $\forall i,j,j^{'}, j\ne j^{'} : x_{ij} \Rightarrow \lnot x_{ij^{'}}$.
208 \:A~nakonec si ohlídáme, aby v~ka¾dém øádku byla alespoò jedna jednièka, klauzulí $\forall i :
209 x_{i1} \lor x_{i2} \lor \ldots \lor x_{in}$.
211 Tímto vynutíme NzMnu $\geq k$, co¾ jsme pøesnì chtìli. Takovýto pøevod je zøejmì polynomiální.
213 \s{Pøíklad matice:} Jako pøíklad pou¾ijeme nezávislou mno¾inu z ukázky nezávislé mno¾iny.
214 Nech» jsou vrcholy grafu oèíslované zleva a zeshora. Hledáme nezávislou mno¾inu velikosti $2$.
215 Matice pak bude vypadat následovnì:
216 $$ \pmatrix{1&0&0&0&0 \cr 0&0&0&1&0}$$
217 \s{Vysvìtlení:} Jako první vrchol mno¾iny bude vybrán vrchol $v_1$, proto v prvním
218 øádku a v prvním sloupci bude $1$. Jako druhý vrchol mno¾iny bude vybrán
219 vrchol $v_4$, proto na druhém øádku a ve ètvrtém sloupci bude $1$. Na ostatních místech bude $0$.
221 \h{4. problém: Klika}
223 \>{\I Vstup:} Graf $G, k \in N$.
225 \>{\I Výstup:} $\exists$ úplný podgraf grafu $G$ na $k$ vrcholech?
226 \figure{klika.eps}{Pøíklad kliky}{2in}
228 \s{Pøevod:} Prohodíme v grafu $G$ hrany a nehrany $\Rightarrow$ (hledání nezávislé mno¾iny $\leftrightarrow$ hledání kliky).
230 \s{Dùvod:} Pokud existuje úplný graf na $k$ vrcholech, tak v~komplementárním grafu tyto vrcholy nejsou spojeny hranou, tj. tvoøí nezávislou mno¾inu,
233 \figure{doplnek_nm.eps}{Prohození hran a nehran}{2in}
236 \h{5. problém: 3,3-SAT}
237 \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.
239 \s{Pøevod 3-SAT na 3,3-SAT:}
240 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:
242 (\lnot x_1 \lor x_2),
243 (\lnot x_2 \lor x_3),
244 (\lnot x_3 \lor x_4),
246 (\lnot x_{k-1} \lor x_k),
247 (\lnot x_k \lor x_1),
253 (x_1 \Rightarrow x_2),
254 (x_2 \Rightarrow x_3),
255 (x_3 \Rightarrow x_4),
257 (x_{k-1} \Rightarrow x_k),
258 (x_k \Rightarrow x_1).
261 Tímto zaruèíme, ¾e v¹echny nové promìnné budou mít stejnou hodnotu.
263 Mimochodem, mù¾eme rovnou zaøídit, ¾e ka¾dý literál se vyskytuje nejvíce dvakrát (tedy ¾e
264 ka¾dá promìnná se vyskytuje alespoò jednou pozitivnì a alespoò jednou negativnì). Pokud by
265 se nìjaká promìnná objevila ve~tøech stejných literálech, mù¾eme na~ni
266 také pou¾ít ná¹ trik a nahradit ji tøemi promìnnými. V~nových klauzulích se pak bude
267 vyskytovat jak pozitivnì, tak negativnì.
269 \h{6. problém: 3D párování (3D matching)}
271 \>{\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).
273 \>{\I Výstup:} Perfektní podmno¾ina trojic -- tj. taková podmno¾ina trojic, která obsahuje v¹echna $K$, $H$ a $Z$.
275 \>Uká¾eme, jak na tento problém pøevést 3,3-SAT (ov¹em to a¾ na dal¹í pøedná¹ce).
277 \figure{3d_parovani.eps}{Ukázka 3D párování}{3in}
279 \s{Závìr:} Obrázek ukazuje problémy, jimi¾ jsme se dnes zabývali, a vztahy mezi tìmito problémy.
280 \figure{prevody.eps}{Pøevody mezi problémy}{3in}
282 \h{NP-úplné problémy}
284 Dosud jsme zkoumali problémy, které se nás ptaly na to, jestli nìco existuje.
285 Napøíklad jsme dostali formuli a problém splnitelnosti se nás ptal, zda
286 existuje ohodnocení promìnných takové, ¾e formule platí. Nebo v~pøípadì
287 nezávislých mno¾in jsme dostali graf a èíslo $k$ a ptali jsme se, jestli
288 v~grafu existuje nezávislá mno¾ina, která obsahuje alespoò~$k$ vrcholù.
289 Tyto otázky mìly spoleèné to, ¾e kdy¾ nám nìkdo napovìdìl nìjaký objekt, umìli
290 jsme efektivnì øíci, zda je to ten, který hledáme. Napøíklad pokud dostaneme
291 ohodnocení promìnných logické formule, staèí jen dosadit a spoèítat, kde
292 formule dá \<true> nebo \<false>. Zjistit, ¾e nìjaký objekt je ten, který
293 hledáme, umíme efektivnì. Tì¾ké na tom je takový objekt najít. Co¾ vede
294 k~definici obecných vyhledávacích problémù, kterým se øíká tøída problémù NP.
295 Nadefinujeme si ji poøádnì, ale nejdøíve zaèneme tro¹ièku jednodu¹¹í tøídou.
297 \s{Definice:} P je {\I tøída rozhodovacích problémù}, které jsou øe¹itelné
298 v~polynomiálním èase. Jinak øeèeno, problém
299 $L \in {\rm P} \Leftrightarrow \exists $ polynom $f$ a~$\exists$ algoritmus~$A$
300 takový, ¾e $\forall x: L(x)=A(x)$ a $A(x)$ dobìhne v~èase $\O(f(x))$.
302 Tøída P tedy odpovídá tomu, o èem jsme se shodli, ¾e umíme efektivnì øe¹it.
303 Nadefinujme nyní tøídu NP:
305 \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
306 $K\in{\rm P}$ a $\exists$ polynom $g$ takový, ¾e pro
307 $\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$.
309 \s{Pozorování:} Splnitelnost logických formulí je v~NP. Staèí si toti¾ nechat napovìdìt, jak
310 ohodnotit jednotlivé promìnné a pak ovìøit, jestli je formule splnìna. Nápovìda je polynomiálnì
311 velká (dokonce lineárnì), splnìní zkontrolujeme také v~lineárním èase. Odpovíme tedy ano právì
312 tehdy, existuje-li nápovìda, která nás pøesvìdèí, èili pokud je formule splnitelná.
314 \s{Pozorování:} Tøída P le¾í uvnitø NP.
315 V~podstatì øíkáme, ¾e kdy¾ máme problém, který umíme øe¹it v~polynomiálním èase
316 bez nápovìdy, tak to zvládneme v~polynomiálním èase i s~nápovìdou.
318 Problémy z minulé pøedná¹ky jsou v¹echny v NP (napø. pro nezávislou
319 mno¾inu je onou nápovìdou pøímo mno¾ina vrcholù deklarující nezávislost),
320 o jejich pøíslu¹nosti do P ale nevíme nic.
321 Brzy uká¾eme, ¾e to jsou v jistém smyslu nejtì¾¹í problémy v~NP.
324 \s{Definice:} Problém $L$ je NP-{\I tì¾ký} právì tehdy, kdy¾ je na~nìj pøevoditelný
325 ka¾dý problém z~NP (viz definici pøevodù z minulé pøedná¹ky).
327 Rozmyslete si, ¾e pokud umíme øe¹it nìjaký NP-tì¾ký problém v~polynomiálním èase,
328 pak umíme vyøe¹it v~polynomiálním èase v¹e v~NP, a tedy ${\rm P}={\rm NP}$.
330 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é.
332 \s{Definice:} Problém $L$ je NP-{\I úplný} právì tehdy, kdy¾ $L$ je NP-tì¾ký a $L \in {\rm NP}$.
334 NP-úplné problémy jsou tedy ve~své podstatì nejtì¾¹í problémy, které le¾í v~NP.
335 Kdybychom umìli vyøe¹it nìjaký NP-úplný problém v~polynomiálním èase, pak
336 v¹echno v~NP je øe¹itelné v~polynomiálním èase. Bohu¾el to, jestli nìjaký
337 NP-úplný problém lze øe¹it v~polynomiálním èase, se neví. Otázka, jestli
338 ${\rm P}={\rm NP}$, je asi nejznámìj¹í otevøený problém v~celé teoretické
341 Kde ale nìjaký NP-úplný problém vzít? K~tomu se nám bude velice hodit následující vìta:
343 \s{Vìta (Cookova):} SAT je NP-úplný.
345 \>Dùkaz je znaènì technický, pøibli¾nì ho naznaèíme pozdìji. Pøímým dùsledkem
346 Cookovy vìty je, ¾e cokoli v~NP je pøevoditelné na SAT.
347 K dokazování NP-úplnosti dal¹ích problémù pou¾ijeme následující vìtièku:
349 \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ý.
352 Tuto vìtièku staèí dokázat pro NP-tì¾kost, NP-úplnost plyne okam¾itì z~toho, ¾e
353 problémy jsou NP-tì¾ké a le¾í v~NP (podle pøedpokladu).
355 Víme, ¾e $L$ se dá pøevést na~$M$ nìjakou funkcí~$f$. Jeliko¾ $L$ je NP-úplný,
356 pak pro ka¾dý problém $Q\in{\rm NP}$ existuje nìjaká funkce~$g$, která pøevede
357 $Q$ na~$L$. Staèí tedy slo¾it funkci~$f$ s~funkcí~$g$, èím¾ získáme funkci pracující
358 opìt v~polynomiálním èase, která pøevede~$Q$ na~$M$. Ka¾dý problém z~NP se tedy
359 dá pøevést na problém~$M$.
362 \s{Dùsledek:} Cokoliv, na co jsme umìli pøevést SAT, je také NP-úplné.
363 Napøíklad nezávislá mno¾ina, rùzné varianty SATu, klika v~grafu~\dots
365 Jak taková tøída NP vypadá? Pøedstavme si v¹echny problémy tøídy NP, jakoby seøazené
366 shora dolu podle obtí¾nosti problémù (tedy navzdor gravitaci), kde porovnání dvou
367 problémù urèuje pøevoditelnost (viz obrázek).
369 \figure{p-np.eps}{Struktura tøídy NP}{2.5cm}
371 Obecnì mohou nastat dvì situace, proto¾e nevíme, jestli ${\rm P}={\rm NP}$.
372 Jestli ano, pak v¹echno je jedna a ta samá tøída. To by bylo v nìkterých
373 pøípadech nepraktické, napø. ka¾dá ¹ifra by byla jednodu¹e rozlu¹titelná.
374 \foot{Poznámka o ¹ifrách -- libovolnou funkci vyèíslitelnou v polynomiálním
375 èase bychom umìli v polynomiálním èase také invertovat.}
376 Jestli ne, NP-úplné problémy urèitì nele¾í v P, tak¾e P a NP-úplné problémy
377 jsou dvì disjunktní èásti NP. Také se dá dokázat (to dìlat nebudeme, ale je
378 dobré to vìdìt), ¾e je¹tì nìco le¾í mezi nimi, tedy ¾e existuje problém, který
379 je v~NP, není v~P a není NP-úplný (dokonce je takových problémù nekoneènì mnoho,
380 v nekoneènì tøídách).
382 \s{Katalog NP-úplných problémù}
384 Uká¾eme si nìkolik základních NP-úplných problémù. O~nìkterých jsme to dokázali
385 na~minulé pøedná¹ce, o~dal¹ích si to doká¾eme nyní, zbylým se na~zoubek podíváme
391 \:SAT (splnitelnost logických formulí v~CNF)
392 \:3-SAT (ka¾dá klauzule obsahuje max.~3 literály)
393 \:3,3-SAT (a navíc ka¾dá promìnná se vyskytuje nejvý¹e tøikrát)
394 \:SAT pro obecné formule (nejen CNF)
395 \:Obvodový SAT (není to formule, ale obvod)
399 \:Nezávislá mno¾ina (existuje mno¾ina alespoò~$k$ vrcholù taková, ¾e ¾ádné dva nejsou propojeny hranou?)
400 \:Klika (existuje úplný podgraf na~$k$ vrcholech?)
401 \: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?)
402 \:Barvení grafu (lze obarvit vrcholy $k$~barvami tak, aby vrcholy stejné barvy nebyly nikdy spojeny hranou? NP-úplné u¾ pro~$k=3$)
403 \:Hamiltonovská cesta (cesta obsahující v¹echny vrcholy [právì jednou])
404 \:Hamiltonovská kru¾nice (kru¾nice, která nav¹tíví v¹echny vrcholy [právì jednou])
408 \:Batoh (nejjednodu¹¹í verze: dána mno¾ina èísel, zjistit, zda existuje podmno¾ina se zadaným souètem)
409 \:Batoh -- optimalizace (podobnì jako u pøedchozího problému, ale místo mno¾iny èísel máme mno¾inu
410 pøedmìtù s vahami a cenami, chceme co nejdra¾¹í podmno¾inu její¾ váha nepøesáhne zadanou kapacitu
412 \:Loupe¾níci (lze rozdìlit danou mno¾inu èísel na~dvì podmno¾iny se stejným souètem)
413 \:$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\}$)
414 \:Celoèíselné lineární programování (existuje vektor nezáporných celoèísených $x$ takový, ¾e $Ax \leq b$ ?)
418 Nyní si uká¾eme, jak pøevést SAT na nìjaký problém. Kdy¾ chceme ukázat, ¾e na
419 nìco se dá pøevést SAT, potøebujeme obvykle dvì vìci:
420 konstrukci, která bude simulovat promìnné, tedy nìco, co nabývá dvou stavù
421 \<true>/\<false>; a nìco, co bude reprezentovat klauzule a umí zaøídit, aby
422 ka¾dá klauzule byla splnìna alespoò jednou promìnnou.
423 Roz¹iøme tedy ná¹ katalog problémù o následující:
424 \h{3D párování (3D matching)}
426 \>{\I Vstup:} Tøi mno¾iny, napø. $K$ (kluci), $H$ (holky), $Z$ (zvíøátka) a
427 mno¾ina $T$ kompatibilních trojic (tìch, kteøí se spolu snesou),
428 tj. $T \subseteq K\times H\times Z$.
430 \>{\I Výstup:} Perfektní podmno¾ina trojic $P\subseteq K\times H \times Z$ --
431 tj. taková podmno¾ina trojic, ¾e $(\forall k\in K\ \exists !p\in P: k\in p)
432 \wedge(\forall h\in H\ \exists !p\in P: h\in p)
433 \wedge(\forall z\in Z\ \exists !p\in P: z\in p)$ -- tedy ka¾dý byl vybrán
437 \h{ Uká¾eme, jak na 3D-párování pøevést 3,3-SAT }
439 Uva¾ujme takovouto konfiguraci:
443 \>4 zvíøátka, 2 kluci, 2 dívky a 4 trojice, které oznaèíme $A, B, C, D$.
444 Je¹tì pøedpokládáme, ¾e zvíøátka
445 se mohou úèastnit nìjakých jiných trojic, ale
446 tito ètyøi lidé se vyskytují pouze v~tìchto ètyøech trojicích a~nikde jinde.
447 V¹imneme si, ¾e existují právì dvì mo¾nosti, jak tento obrázek spárovat.
448 Abychom spárovali kluka $k_1$, tak si musíme vybrat $A$ nebo $B$. Kdy¾ si
449 vybereme $A$, $k_1$ i $d_2$ u¾ jsou spárovaní tak¾e si nesmíme vybrat $B$ ani
450 $D$. Pak jediná mo¾nost, jak spárovat $d_1$ a~$k_2$ je $C$. Jedna mo¾nost je
451 tedy vybrat si $A$ a $C$ a jeliko¾ je obrázek symetrický, tak kdy¾ vybereme
452 místo $A$ trojici $B$, dostaneme $B$ a~$D$. V¾dy si tedy vybereme dvì protìj¹í
455 Tyto konfigurace budeme pou¾ívat k~reprezentaci promìnných. Pro ka¾dou
456 promìnnou si nakreslíme takový obrázek a~to, ¾e $A$ bude spárované s~$C$, bude
457 odpovídat tomu, ¾e $x=1$, a~spárování $B$ a~$D$ bude odpovídat
459 pou¾ili $A$ a~$C$, zvíøata se sudými èísly, tj. $z_2$ a~$z_4$, horní a~dolní,
460 jsou nespárovaná a~pokud jsme pou¾ili $B$ a~$D$, zvíøátka $z_1$ a~$z_3$ zùstala
461 nespárovaná. Pøes tato nespárovaná zvíøátka mù¾eme pøedávat informaci, jestli
462 promìnná $x$ má hodnotu \<true> nebo \<false> do dal¹ích èástí vstupu.
464 Zbývá vymyslet, jak reprezentovat klauzule. Klauzule jsou trojice popø. dvojice
465 literálù, napø. $\kappa = (x \lor y \lor \lnot r)$, kde
466 potøebujeme zajistit, aby $x$ bylo nastavené na $1$ nebo $y$ bylo nastavené
467 na~$1$ nebo $r$ na $0$.
469 \fig{klauzule.eps}{4cm}
471 \>Pro takovouto klauzuli si poøídíme dvojici kluk-dívka, kteøí budou figurovat
472 ve tøech trojicích se tøemi rùznými zvíøátky, co¾ mají být volná zvíøátka
473 z~obrázkù pro pøíslu¹né promìnné (podle toho, má-li se promìnná vyskytnout
474 s negací nebo ne). A~zaøídíme to tak, aby ka¾dé zvíøátko bylo
475 pou¾ité maximálnì v~jedné takové trojici, co¾ jde proto, ¾e ka¾dý literál se
476 vyskytuje maximálnì dvakrát a~pro ka¾dý literál máme dvì volná zvíøátka,
477 z~èeho¾ plyne, ¾e zvíøátek je dost pro v¹echny klauzule. Pro dvojice se postupuje
480 Je¹tì nám ale urèitì zbude $2p-k$ zvíøátek, kde $p$ je poèet promìnných, $k$
481 poèet klauzulí -- ka¾dá promìnná vyrobí 4 zvíøátka, klauzule zba¹tí jedno
482 a samotné ohodnocení 2 zvíøátka -- tak pøidáme je¹tì $2p-k$ párù
483 kluk-dìvèe, kteøí milují
484 v¹echna zvíøátka, a~ti vytvoøí zbývající trojice.
486 Pokud formule byla splnitelná, pak ze splòujícího ohodnocení mù¾eme vyrobit
487 párování s~na¹í konstrukcí. Obrázek pro ka¾dou promìnnou spárujeme podle
488 ohodnocení, tj. promìnná je $0$ nebo $1$ a~pro ka¾dou klauzuli si vybereme
489 nìkterou z~promìnných, kterými je ta klauzule splnìna. Funguje to ale
490 i~opaènì: Kdy¾ nám nìkdo dá párovaní v~na¹í konstrukci, pak z nìho doká¾eme
491 vyrobit splòující ohodnocení dané formule. Podíváme se, v~jakém stavu je
492 promìnná, a~to je v¹echno. Z~toho, ¾e jsou správnì spárované klauzule, u¾
493 okam¾itì víme, ¾e jsou v¹echny splnìné.
495 Zbývá ovìøit, ¾e na¹e redukce funguje v~polynomiálním èase. Pro ka¾dou klauzuli
496 spotøebujeme konstantnì mnoho èasu, $2p-k$ je také polynomiálnì mnoho a~kdy¾ v¹e
497 seèteme, máme polynomiální èas vzhledem k~velikosti vstupní formule. Tím je
498 pøevod hotový a~mù¾eme 3D-párování zaøadit mezi NP-úplné problémy.
504 \h{Náznak dùkazu Cookovy vìty}
506 Abychom mohli budovat teorii NP-úplnosti, potøebujeme alespoò jeden problém,
507 o kterém doká¾eme, ¾e je NP-úplný, z definice. Cookova vìta øíká o NP-úplnosti
508 SAT-u, ale nám se to hodí dokázat o tro¹ku jiném problému -- {\I obvodovém SAT-u}.
510 \>{\I Obvodový SAT} je splnitelnost, která nepracuje s~formulemi, ale s~booleovskými
511 obvody (hradlovými sítìmi). Ka¾dá formule se dá pøepsat do booleovského obvodu,
512 který ji poèítá, tak¾e dává smysl zavést splnitelnost i pro obvody. Na¹e obvody
513 budou mít nìjaké vstupy a~jenom jeden výstup. Budeme se ptát, jestli se vstupy
514 tohoto obvodu dají nastavit tak, abychom na výstupu dostali \<true>.
516 \>Nejprve doká¾eme NP-úplnost {\I obvodového SAT-u} a~pak uká¾eme, ¾e se dá
517 pøevést na obyèejný SAT v~CNF. Tím bude dùkaz Cookovy vìty hotový. Zaènìme
520 \s{Lemma:} Nech» $L$ je problém v P. Potom existuje polynom $p$ a algoritmus,
521 který pro $\forall n \ge 0$ spoète v èase $p(n)$ hradlovou sí» $Bn$ s $n$ vstupy
522 a 1 výstupem takovou, ¾e $\forall x \in \{ 0, 1 \}^n : Bn(x) = L(x)$.
525 Náznakem. Na základì zku¹eností z Principù poèítaèù intuitivnì chápeme poèítaèe
526 jako nìjaké slo¾ité booleovské obvody, jejich¾ stav se mìní v~èase. Uva¾me tedy
527 nìjaký problém $L \in {\rm P}$ a polynomiální algoritmus, který ho øe¹í. Pro vstup
528 velikosti~$n$ dobìhne v~èase~$T$ polynomiálním v~$n$ a spotøebuje $\O(T)$ bunìk pamìti.
529 Staèí nám tedy \uv{poèítaè s~pamìtí velkou $\O(T)$}, co¾ je nìjaký booleovský obvod
530 velikosti polynomiální v~$T$, a~tedy i v~$n$. Vývoj v~èase o¹etøíme tak, ¾e sestrojíme~$T$
531 kopií tohoto obvodu, ka¾dá z~nich bude odpovídat jednomu kroku výpoètu a bude
532 propojena s~\uv{minulou} a \uv{budoucí} kopií. Tím sestrojíme booleovský obvod,
533 který bude øe¹it problém~$L$ pro vstupy velikosti~$n$ a bude polynomiálnì velký
537 Pro dùkaz následující vìty si dovolíme drobnou úpravu v~definici tøídy NP.
538 Budeme chtít, aby nápovìda
539 mìla pevnou velikost, závislou pouze na~velikosti vstupu (tedy: $\vert y \vert
540 = g(\vert x \vert)$ namísto $\vert y \vert \le g(\vert x \vert)$). Proè je taková
541 úprava BÚNO? Jistì si dovedete pøedstavit,
542 ¾e pùvodní nápovìdu doplníme na po¾adovanou délku nìjakými \uv{mezerami}, které
543 program ignoruje. (Tedy upravíme program tak, aby mu nevadilo, ¾e dostane na
544 konci nápovìdy nìjak kódované mezery.)
546 \s{Vìta:} Obvodový SAT je NP-úplný.
549 Máme tedy nìjaký problém $L$ z~NP a~chceme dokázat, ¾e $L$ se dá pøevést
550 na~obvodový SAT (tj. NP-tì¾kost). Kdy¾ nám nìkdo pøedlo¾í nìjaký vstup $x$
551 (chápeme jako posloupnost $x_1, x_2, \ldots, x_n$),
552 spoèítáme velikost nápovìdy $g(n)$. Víme, ¾e kontrolní
553 algoritmus~$K$ (který kontroluje, zda nápovìda je správnì) je v~P. Vyu¾ijeme
554 pøedchozí lemma, abychom získali obvod, který pro konkrétní velikost vstupu
555 $x$ poèítá to, co kontrolní algoritmus $K$. Na vstupu tohoto obvodu bude $x$
556 (vstup problému $L$) a~nápovìda~$y$. Na výstupu nám øekne, jestli je nápovìda
557 správná. Velikost vstupu tohoto obvodu bude tedy $p(g(n))$, co¾ je také polynom.
559 \fig{kobvod.eps}{2.3cm}
561 \>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ý.
563 \>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á
564 v~polynomiálním èase pøevést na obvodový SAT.
566 \>Obvodový SAT je v NP triviálnì -- staèí si nechat poradit vstup, sí»
567 topologicky setøídit a v~tomto poøadí poèítat hodnoty hradel.
570 \s{Lemma:} Obvodový SAT se dá pøevést na 3-SAT.
573 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 {\csc and} a {\csc 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ì.
575 \>{\I Pøevod hradla \csc 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é:
576 $$\matrix{ (x \lor y), \cr
577 (\neg{x} \lor \neg{y}). \cr }
579 \vcenter{\hbox{\epsfxsize=0.7cm\epsfbox{not.eps}}}
582 \>{\I Pøevod hradla \csc and}: Hradlo má vstupy $x, y$ a~výstup $z$. Potøebujeme pøidat klauzule, které nám popisují, jak se má hradlo {\csc and} chovat. Tyto vztahy pøepí¹eme do~konjunktivní normální formy:
585 x\ \&\ y \Rightarrow z \cr
586 \neg{x} \Rightarrow \neg{z} \cr
587 \neg{y} \Rightarrow \neg{z} \cr
593 (z \lor \neg{x} \lor \neg{y}) \cr
598 \vcenter{\hbox{\epsfxsize=0.7cm\epsfbox{and.eps}}}
601 \>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 {\csc and} a~{\csc 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.
605 Kdy¾ jsme zavádìli SAT, omezili jsme se jen na formule, které jsou
606 v~konjunktivní normální formì (CNF). Teï u¾ víme, ¾e splnitelnost obecné
607 booleovské formule doká¾eme pøevést na obvodovou splnitelnost a tu pak
608 pøevést na 3-SAT. Opaèný pøevod je samozøejmì triviální, tak¾e obecný SAT
609 je ve~skuteènosti ekvivalentní s~na¹ím \uv{standardním} SATem pro CNF.
projects / ads2.git / blob