3 \prednaska{8}{Pøevody problémù a NP-úplnost}{}
5 \def\prob#1{\h{Problém #1}}
6 \def\inp{\s{Vstup problému:} }
7 \def\outp{\s{Výstup problému:} }
9 \def\cc#1{\hbox{\setfonts[CMSans/]\bf #1}}
13 V¹echny úlohy, které jsme zatím potkali, jsme umìli vyøe¹it algoritmem
14 s~polynomiální èasovou slo¾itostí. V~prvním pøiblí¾ení mù¾eme øíci, ¾e
15 polynomialita docela dobøe vystihuje praktickou pou¾itelnost algoritmu.%
16 \foot{Jistì vás napadne spousta protipøíkladù, jako tøeba algoritmus se
17 slo¾itostí $\O(1.001^n)$, který nejspí¹ je pou¾itelný, aèkoliv není polynomiální,
18 a~jiný se slo¾itostí $\O(n^{100})$, u~kterého je tomu naopak. Ukazuje se,
19 ¾e tyto pøípady jsou velmi øídké, tak¾e u~vìt¹iny problémù ná¹ zjednodu¹ený
20 pohled funguje pøekvapivì dobøe.}
22 Existují tedy polynomiální algoritmy pro v¹echny úlohy? Zajisté ne,
23 jsou dokonce i takové úlohy, je¾ ¾ádným algoritmem vyøe¹it nelze.
24 Ale i mezi tìmi algoritmicky øe¹itelnými potkáme spoustu úloh,
25 pro které zatím ¾ádný polynomiální algoritmus není známý (ale ani neumíme
26 dokázat, ¾e neexistuje). Takové úlohy jsou pøekvapivì èasté, proto se
27 na této pøedná¹ce podíváme na nìkolik typických pøíkladù.
29 Navíc uvidíme, ¾e aèkoliv tyto úlohy neumíme efektivnì øe¹it, jde mezi
30 nimi nalézt zajímavé vztahy a pomocí tìchto vztahù obtí¾nost problémù
31 vzájemnì porovnávat. Z~tìchto úvah vyrùstá i skuteèná teorie slo¾itosti
32 se svými hierarchiemi slo¾itostních tøíd. Mù¾ete tedy následující kapitolu
33 pova¾ovat za malou ochutnávku toho, jak lze k~tøídám problémù pøistupovat.
35 \h{Rozhodovací problémy a pøevody mezi nimi}
37 Aby se nám teorie pøíli¹ nerozko¹atila, omezíme své úvahy na rozhodovací
38 problémy. To jsou úlohy, jejich¾ výstupem je jediný bit -- máme tedy rozhodnout,
39 zda vstup má èi nemá urèenou vlastnost. Vstup pøitom budeme reprezentovat øetìzcem
40 nul a jednièek -- libovolnou jinou \uv{rozumnou} reprezentaci doká¾eme na tyto
41 øetìzce pøevést v~polynomiálním èase. Formálnìji:
43 \s{Definice:} {\I Rozhodovací problém} (zkrácenì {\I problém}) je funkce z~mno¾iny $\{0,1\}^*$ v¹ech
44 øetìzcù nad binární abecedou do mno¾iny $\{0,1\}$.%
45 \foot{Ekvivalentnì bychom se na~problém mohli také dívat jako na nìjakou
46 mno¾inu $A\subseteq \{0,1\}^*$ vstupù, na nì¾ je odpovìï~1. Tento pøístup
47 mají rádi v~teorii automatù.}
49 \s{Pøíklad problému:} {\I Bipartitní párování} -- je dán bipartitní graf
50 a èíslo $k \in {\bb N}$. Zapí¹eme je pomocí øetìzce bitù: graf tøeba maticí
51 sousednosti, èíslo dvojkovì (detaily kódování budeme nadále vynechávat). Máme
52 odpovìdìt, zda v~zadaném grafu existuje párování, které obsahuje alespoò $k$
55 (Otázka, zda existuje párování o~právì~$k$ hranách, je ekvivalentní,
56 proto¾e mù¾eme libovolnou hranu z~párování vypustit a bude to stále párování.)
58 \s{Odboèka:} Èasto nás samozøejmì nejen zajímá, zda párování existuje, ale také
59 chceme nìjaké konkrétní najít. I~to jde pomocí rozhodovací verze problému snadno
60 zaøídit. Podobný postup funguje pro mnoho dal¹ích problémù.
62 Mìjme èernou skøíòku (fungující v polynomiálním èase), která odpoví, zda daný
63 graf má nebo nemá párování o~$k$ hranách. Odebereme z~grafu libovolnou hranu
64 a zeptáme se, jestli i tento nový graf má párovaní velikosti~$k$. Kdy¾ má, pak tato
65 hrana nebyla pro existenci párování potøebná, a~tak ji odstraníme. Kdy¾ naopak
66 nemá (hrana patøí do ka¾dého párování po¾adované velikosti), tak si danou hranu
67 poznamenáme a odebereme nejen ji a její vrcholy, ale také hrany, které do tìchto
68 vrcholù vedly. Toto je korektní krok, proto¾e v pùvodním grafu tyto vrcholy
69 byly navzájem spárované, a tedy nemohou být spárované s~¾ádnými jinými vrcholy.
70 Na~nový graf aplikujeme znovu tentý¾ postup. Výsledkem je mno¾ina hran, které patøí
71 do hledaného párování. Hran, a tedy i iterací na¹eho algoritmu, je polynomiálnì
72 mnoho a skøíòka funguje v polynomiálním èase, tak¾e celý algoritmus je polynomiální.%
73 \foot{Zde se skrývá hlavní dùvod, proè informatici mají tak rádi polynomiální
74 algoritmy. Tøída v¹ech polynomù je toti¾ nejmen¹í tøídou funkcí, která obsahuje
75 v¹echny \uv{základní} funkce (konstanty, $n$, $n^2$, \dots) a je uzavøená na sèítání,
76 odèítání, násobení i skládání funkcí.}
78 \s{Zpìt z~odboèky:} Jak párovací problém vyøe¹it? Vìrni matfyzáckým vtipùm,
79 pøevedeme ho na nìjaký, který u¾ vyøe¹it umíme. To u¾ ostatnì umíme -- na~toky
80 v~sítích. Poka¾dé, kdy¾ se ptáme na existenci párování velikosti alespoò~$k$
81 v~nìjakém bipartitním grafu, umíme efektivnì sestrojit nìjakou sí» a zeptat se,
82 zda v~této síti existuje tok velikosti alespoò~$k$. Chceme tedy pøelo¾it vstup
83 jednoho problému na vstup jiného problému tak, aby odpovìï zùstala stejná.
85 Takovéto pøevody mezi problémy mù¾eme definovat i~obecnìji:
87 \s{Definice:} Jsou-li $A$, $B$ rozhodovací problémy, øíkáme, ¾e $A$ lze {\I
88 pøevést} (neboli {\I redukovat}) na~$B$ (pí¹eme $A \rightarrow B$) právì tehdy,
89 kdy¾ existuje funkce $f: \{0,1\}^* \rightarrow \{0,1\}^*$ taková, ¾e pro v¹echna
90 $x\in \{0,1\}^*$ platí $A(x) = B(f(x))$, a~navíc lze funkci~$f$ spoèítat v~polynomiálním
93 \s{Pozorování:} $A\rightarrow B$ také znamená, ¾e problém~$B$ je alespoò tak tì¾ký
94 jako problém~$A$. Tím myslíme, ¾e kdykoliv umíme vyøe¹it~$B$, je vyøe¹it~$A$ nejvý¹e
95 polynomiálnì obtí¾nìj¹í. Speciálnì platí:
97 \s{Lemma:} Pokud $A\rightarrow B$ a $B$~lze øe¹it v~polynomiálním èase,
98 pak i~$A$ lze øe¹it v~polynomiálním èase.
101 Nech» existuje algoritmus øe¹ící problém~$B$ v~èase $\O(b^k)$, kde $b$~je
102 délka vstupu tohoto problému a $k$~konstanta. Mìjme dále funkci~$f$ pøevádìjící
103 $A$ na~$B$ v~èase $\O(a^\ell)$ pro vstup délky~$a$. Chceme-li nyní spoèítat
104 $A(x)$ pro nìjaký vstup~$x$ délky~$a$, spoèítáme nejprve $f(x)$. To bude trvat
105 $\O(a^\ell)$ a vyjde výstup délky takté¾ $\O(a^\ell)$ -- del¹í bychom v~daném èase
106 ani nestihli vypsat. Tento vstup pak pøedáme algoritmu pro problém~$B$,
107 který nad ním stráví èas $\O((a^\ell)^k) = \O(a^{k\ell})$. Celkový èas výpoètu
108 tedy èiní $\O(a^\ell + a^{k\ell})$, co¾ je polynom v~délce pùvodního vstupu.
111 Relace pøevoditelnosti jistým zpùsobem porovnává problémy podle obtí¾nosti.
112 Nabízí se pøedstava, ¾e se jedná o~uspoøádání na mno¾inì v¹ech problémù. Je tomu
115 \s{Pozorování:} O~relaci \uv{$\rightarrow$} platí:
117 \:{\I Je reflexivní} ($A\rightarrow A$) -- úlohu mù¾eme pøevést na tuté¾ identickým zobrazením.
118 \:{\I Je tranzitivní} ($A\rightarrow B \land B\rightarrow C \Rightarrow A\rightarrow C$) --
119 pokud funkce~$f$ pøevádí $A$ na~$B$ a funkce~$g$ pøevádí $B$ na~$C$, pak funkce $g\circ f$
120 pøevádí $A$ na~$C$. Slo¾ení dvou polynomiálnì vyèíslitelných funkcí je zase polynomiálnì
121 vyèíslitelná funkce, jak u¾ jsme zpozorovali v~dùkazu pøedchozího lemmatu.
122 \:{\I Není antisymetrická} -- napøíklad problémy \uv{na vstupu je øetìzec zaèínající nulou}
123 a \uv{na vstupu je øetìzec konèící nulou} lze mezi sebou pøevádìt obìma smìry.
124 \:Existují {\I navzájem nepøevoditelné problémy} -- tøeba mezi problémy \uv{na ka¾dý vstup
125 odpovìz~0} a \uv{na ka¾dý vstup odpovìz~1} nemù¾e existovat pøevod ani jedním smìrem.
128 \>Relacím, které jsou reflexivní a tranzitivní, ale obecnì nesplòují antisymetrii,
129 se øíká {\I kvaziuspoøádání}. Pøevoditelnost je tedy èásteèné kvaziuspoøádání na mno¾inì
130 v¹ech problémù.\foot{Kdybychom z~nìj chtìli vyrobit opravdové (by» èásteèné) uspoøádání,
131 mohli bychom definovat ekvivalenci $A\sim B \equiv A\rightarrow B \land B\rightarrow A$
132 a relaci pøevoditelnosti zavést jen na tøídách této ekvivalence. Taková pøevoditelnost
133 by u¾ byla slabì antisymetrická. To je v~matematice dost bì¾ný trik, øíká se mu {\I faktorizace} kvaziuspoøádání.}
135 Nyní se ji¾ podíváme na pøíklady nìkolika problémù, které se obecnì pova¾ují
136 za tì¾ké. Uvidíme, ¾e ka¾dý z~nich je mo¾né pøevést na v¹echny ostatní, tak¾e
137 z~na¹eho \uv{polynomiálního} pohledu jsou stejnì obtí¾né.
139 \prob{SAT -- splnitelnost (satisfiability) logických formulí v~CNF}
141 Mìjme nìjakou logickou formuli s~promìnnými a logickými spojkami. Zajímá
142 nás, je-li tato formule {\I splnitelná,} tedy zda lze za promìnné dosadit
143 0 a~1 tak, aby formule dala výsledek~1 (byla {\I splnìna}).
145 Zamìøíme se na formule ve~speciálním tvaru, v~takzvané {\I konjunktivní normální
149 \:{\I formule} je slo¾ena z~jednotlivých {\I klauzulí} oddìlených spojkou~$\land$,
150 \:ka¾dá {\I klauzule} je slo¾ená z {\I literálù} oddìlených $\lor$,
151 \:ka¾dý {\I literál} je buïto promìnná nebo její negace.
154 \inp Formule $\psi$ v konjunktivní normální formì.
156 \outp Existuje-li dosazení 0 a~1 za promìnné tak, aby $\psi(\ldots) = 1$.
158 \s{Pøíklad:} Formule $(x\lor y\lor z) \land (\lnot x \lor y \lor z) \land (x \lor \lnot y \lor z) \land (x \lor y \lor \lnot z)$
159 je splnitelná, staèí nastavit napøíklad $x=y=z=1$ (jaká jsou ostatní splòující
160 ohodnocení?). Naproti tomu formule $(x\lor y) \land (x\lor \lnot y)
161 \land \lnot x$ splnitelná není, co¾ snadno ovìøíme tøeba vyzkou¹ením v¹ech
162 ètyø mo¾ných ohodnocení.
164 \s{Poznámka:} Co kdybychom chtìli zjistit, zda je splnitelná nìjaká formule,
165 která není v~CNF? V~logice se dokazuje, ¾e ke~ka¾dé formuli lze najít ekvivalentní
166 formuli v~CNF, ale pøi tom se bohu¾el formule mù¾e a¾ exponenciálnì prodlou¾it.
167 Pozdìji uká¾eme, ¾e pro ka¾dou formuli~$\chi$ existuje nìjaká formule $\chi'$ v~CNF,
168 která je splnitelná právì tehdy, kdy¾ je $\chi$ splnitelná. Formule $\chi'$ pøitom
169 bude dlouhá $\O(\vert\chi\vert)$, ale budou v~ní nìjaké nové promìnné.
171 \prob{3-SAT -- splnitelnost formulí s~krátkými klauzulemi}
173 Pro SAT zatím není známý ¾ádný polynomiální algoritmus. Co kdybychom zkusili
174 problém trochu zjednodu¹it a uva¾ovat pouze formule ve~speciálním tvaru?
176 Povolíme tedy na vstupu pouze takové formule v~CNF, jejich¾ ka¾dá klauzule obsahuje
177 nejvý¹e tøi literály. Uká¾eme, ¾e tento problém je stejnì tì¾ký jako pùvodní SAT.
179 \s{Pøevod 3-SATu na SAT:}
180 Jeliko¾ 3-SAT je speciálním pøípadem SATu, poslou¾í tu jako pøevodní funkce
183 \s{Pøevod SATu na 3-SAT:}
184 Nech» se ve~formuli vyskytuje nìjaká \uv{¹patná} klauzule o~$k>3$ literálech.
185 Mù¾eme ji zapsat ve~tvaru $(\alpha\lor\beta)$, kde $\alpha$ obsahuje 2~literály
186 a $\beta$ $k-2$ literálù. Poøídíme si novou promìnnou~$x$ a klauzuli nahradíme
187 dvìma novými $(\alpha\lor x)$ a $(\beta\lor\lnot x)$. První z~nich obsahuje 3~literály,
188 tedy je dobrá. Druhá má $k-1$ literálù, tak¾e mù¾e být stále ¹patná, ale aspoò je
189 krat¹í, tak¾e mù¾eme postup opakovat.
191 Takto postupnì nahradíme v¹echny ¹patné klauzule dobrými, co¾ bude trvat nejvý¹e
192 polynomiálnì dlouho: klauzuli délky~$k$ rozebereme po $k-3$ krocích, ¹patných
193 klauzulí je lineárnì s~délkou formule.
195 Zbývá ukázat, ¾e nová formule je splnitelná právì tehdy, byla-li splnitelná
196 formule pùvodní. K~tomu staèí ukázat, ¾e ka¾dý jednotlivý krok pøevodu splnitelnost
199 Pokud pùvodní formule byla splnitelná, uva¾me nìjaké splòující ohodnocení promìnných.
200 Uká¾eme, ¾e v¾dy mù¾eme novou promìnnou~$x$ nastavit tak, aby vzniklo splòující
201 ohodnocení nové formule. Víme, ¾e klauzule $(\alpha\lor\beta)$ byla splnìna. Proto
204 \:Buïto $\alpha=1$. Pak polo¾íme $x=0$, tak¾e $(\alpha\lor x)$ bude splnìna díky~$\alpha$
205 a $(\beta\lor\lnot x)$ díky~$x$.
206 \:Anebo $\alpha=0$, a~tedy $\beta=1$. Pak polo¾íme $x=1$, èím¾ bude $(\alpha\lor x)$ splnìna díky~$x$,
207 zatímco $(\beta\lor\lnot x)$ díky~$\beta$.
209 \>Ostatní klauzule budou stále splnìny.
211 V~opaèném smìru: pokud dostaneme splòující ohodnocení nové formule, umíme z~nìj získat
212 splòující ohodnocení formule pùvodní. Uká¾eme, ¾e staèí zapomenout promìnnou~$x$.
213 V¹echny klauzule, kterých se na¹e transformace netýká, jsou nadále splnìné.
214 Co klauzule $(\alpha\lor\beta)$?
216 \:Buïto $x=0$, pak musí být $(\alpha\lor x)$ splnìna díky~$\alpha$, tak¾e
217 $(\alpha\lor\beta)$ je také splnìna díky~$\alpha$.
218 \:Anebo $x=1$, pak musí být $(\beta\lor\lnot x)$ splnìna díky~$\beta$, tak¾e
219 i $(\alpha\lor\beta)$ je splnìna.
222 \>Tím je pøevod hotov, SAT a 3-SAT jsou tedy ekvivalentní.
224 \prob{NzMna -- nezávislá mno¾ina vrcholù v~grafu}
226 \s{Definice:} Mno¾ina vrcholù grafu je {\I nezávislá,} pokud ¾ádné dva
227 vrcholy le¾ící v~této mno¾inì nejsou spojeny hranou. (Jinými slovy nezávislá
228 mno¾ina indukuje podgraf bez hran.)
230 \figure{nezmna.eps}{Pøíklad nezávislé mno¾iny}{0.7in}
232 \>Na samotnou existenci nezávislé mno¾iny se nemá smysl ptát -- prázdná mno¾ina
233 èi libovolný jeden vrchol jsou v¾dy nezávislé. Zajímavé ale je, jestli graf obsahuje
234 dostateènì velkou nezávislou mno¾inu.
236 \inp Neorientovaný graf $G$ a èíslo $k \in {\bb N}$.
238 \outp Zda existuje nezávislá mno¾ina $A \subseteq V(G)$ velikosti alespoò~$k$.
240 \s{Pøevod 3-SAT $\rightarrow$ NzMna:}
241 Dostaneme formuli a máme vytvoøit graf, v~nìm¾ se bude nezávislá mno¾ina
242 urèené velikosti nacházet právì tehdy, je-li formule splnitelná.
243 My¹lenka pøevodu bude jednoduchá: z~ka¾dé klauzule budeme chtít vybrat jeden
244 literál, jeho¾ nastavením klauzuli splníme. Samozøejmì si musíme dát pozor, abychom
245 v~rùzných klauzulích nevybírali konfliktnì, tj. jednou~$x$ a podruhé~$\lnot x$.
247 Jak to pøesnì zaøídit:
248 pro ka¾dou z~$k$~klauzulí zadané formule vytvoøíme trojúhelník a jeho vrcholùm
249 pøiøadíme literály klauzule. (Pokud by klauzule obsahovala ménì literálù,
250 prostì nìkteré vrcholy trojúhelníka sma¾eme.) Navíc spojíme hranami v¹echny
251 dvojice konfliktních literálù ($x$ a~$\lnot x$) z~rùzných trojúhelníkù.
253 V~tomto grafu se budeme ptát po nezávislé mno¾inì velikosti alespoò~$k$.
254 Jeliko¾ z~ka¾dého trojúhelníka mù¾eme do~nezávislé mno¾iny vybrat nejvý¹e jeden vrchol,
255 jediná mo¾nost, jak dosáhnout po¾adované velikosti, je vybrat z~ka¾dého právì jeden
256 vrchol. Uká¾eme, ¾e taková nezávislá mno¾ina existuje právì tehdy, je-li formule splnitelná.
258 Máme-li splòující ohodnocení formule, mù¾eme z~ka¾dé klauzule vybrat jeden splnìný
259 literál. Do nezávislé mno¾iny umístíme vrcholy odpovídající tìmto literálùm. Je jich
260 právì~$k$. Jeliko¾ ka¾dé dva vybrané vrcholy le¾í v~rùzných trojúhelnících a nikdy
261 nemù¾e být splnìný souèasnì literál a jeho negace, mno¾ina je opravdu nezávislá.
263 A~opaènì: Kdykoliv dostaneme nezávislou mno¾inu velikosti~$k$, vybereme literály
264 odpovídající vybraným vrcholùm a pøíslu¹né promìnné nastavíme tak, abychom tyto
265 literály splnili. Díky hranám mezi konfliktními literály se nikdy nestane, ¾e bychom
266 potøebovali promìnnou nastavit souèasnì na~0 a na~1. Zbývající promìnné ohodnotíme
267 libovolnì. Jeliko¾ jsme v~ka¾dé klauzuli splnili alespoò jeden literál, jsou
268 splnìny v¹echny klauzule, a~tedy i celá formule.
270 Pøevod je tedy korektní, zbývá rozmyslet, ¾e bì¾í v~polynomiálním èase:
271 Poèet vrcholù grafu odpovídá poètu literálù ve formuli, poèet hran je maximálnì
272 kvadratický. Ka¾dý vrchol i hranu pøitom sestrojíme v~polynomiálním èase, tak¾e
273 celý pøevod je také polynomiální.
275 \figure{nezmna_graf.eps}{Graf pro formuli $(x \lor y \lor z) \land (x \lor \lnot y \lor \lnot z) \land (\lnot x \lor \lnot y \lor p)$}{3in}
277 \s{Pøevod NzMna $\rightarrow$ SAT:}
278 Dostaneme graf a èíslo~$k$, chceme vytvoøit formuli, která je splnitelná právì
279 tehdy, pokud se v~grafu nachází nezávislá mno¾ina o~alespoò~$k$ vrcholech.
280 Tuto formuli sestrojíme následovnì.
282 Vrcholy grafu oèíslujeme od~1 do~$n$ a poøídíme si pro nì promìnné $v_1, \ldots, v_n$,
283 které budou indikovat, zda byl pøíslu¹ný vrchol vybrán do nezávislé mno¾iny
284 (pøíslu¹né ohodnocení promìnných tedy bude odpovídat charakteristické funkci nezávislé mno¾iny).
286 Aby mno¾ina byla opravdu nezávislá, pro ka¾dou hranu $ij \in E(G)$ pøidáme klauzuli
287 $(\lnot v_i \lor \lnot v_j)$.
289 Je¹tì potøebujeme zkontrolovat, ¾e mno¾ina je dostateènì velká. To neumíme provést
290 pøímo, ale pou¾ijeme lest: vyrobíme matici promìnných~$X$ tvaru~$k\times n$, která bude popisovat
291 oèíslování vrcholù nezávislé mno¾iny èísly od~1 do~$k$. Konkrétnì $x_{ij}$ bude øíkat,
292 ¾e v~poøadí $i$-tý prvek nezávislé mno¾iny je vrchol~$j$. K~tomu potøebujeme zaøídit:
295 \:Aby v~ka¾dém sloupci byla nejvý¹e jedna jednièka. Na to si poøídíme klauzule
296 $(x_{i,j} \Rightarrow \lnot x_{i',j})$ pro $i'\ne i$.
297 (Jsou to implikace, ale mù¾eme je zapsat i jako disjunkce, proto¾e $a\Rightarrow b$
298 je toté¾ jako $\lnot a \lor b$.)
299 \:Aby v~ka¾dém øádku le¾ela právì jedna jednièka. Nejprve zajistíme nejvý¹e jednu
300 klauzulemi $(x_{i,j} \Rightarrow \lnot x_{i,j'})$ pro $j'\ne j$.
301 Pak pøidáme klauzule $(x_{i,1}\lor x_{i,2}\lor \ldots \lor x_{i,n})$,
302 které po¾adují alespoò jednu jednièku v~øádku.
303 \:Vztah mezi oèíslováním a nezávislou mno¾inou: pøidáme klauzule $x_{i,j} \Rightarrow v_j$.
304 (V¹imnìte si, ¾e nezávislá mno¾ina mù¾e obsahovat
305 i neoèíslované prvky, ale to nám nevadí. Dùle¾ité je, aby jich mìla $k$~oèíslovaných.)
308 Správnost pøevodu je zøejmá, ovìøme je¹tì, ¾e probíhá v~polynomiálním èase.
309 To plyne z~toho, ¾e vytvoøíme polynomiálnì mnoho klauzulí a ka¾dou z~nich
310 stihneme vypsat v~lineárním èase.
312 Dokázali jsme tedy, ¾e testování existence nezávislé mno¾iny je stejnì tì¾ké
313 jako testování splnitelnosti formule. Pojïme se podívat na dal¹í problémy.
315 \prob{Klika -- úplný podgraf}
317 Podobnì jako nezávislou mno¾inu mù¾eme v~grafu hledat i {\I kliku} -- úplný
318 podgraf dané velikosti.
320 \inp Graf $G$ a èíslo $k \in N$.
322 \outp Existuje-li úplný podgraf grafu $G$ na alespoò $k$ vrcholech.
324 \figure{klika.eps}{Pøíklad kliky}{2in}
326 Tento problém je ekvivalentní s~hledáním nezávislé mno¾iny. Pokud v~grafu prohodíme
327 hrany a nehrany, stane se z~ka¾dé kliky a nezávislá mno¾ina a naopak. Pøevodní funkce
328 tedy zneguje hrany a ponechá èíslo~$k$.
330 \figure{doplnek_nm.eps}{Prohození hran a nehran}{2in}
332 \prob{3,3-SAT -- splnitelnost s~malým poètem výskytù}
334 Ne¾ se pustíme do~dal¹ího kombinatorického problému, pøedvedeme je¹tì jednu
335 speciální variantu SATu, se kterou se nám bude pracovat pøíjemnìji.
337 Ji¾ jsme ukázali, ¾e SAT zùstane stejnì tì¾ký, omezíme-li se na formule
338 s~klauzulemi délky nejvý¹e~3. Teï budeme navíc po¾adovat, aby se ka¾dá promìnná
339 vyskytovala v~maximálnì tøech literálech. Tomuto problému se øíká 3,3-SAT.
341 \s{Pøevod 3-SATu na 3,3-SAT:}
342 Pokud se promìnná $x$ vyskytuje v~$k > 3$ literálech, nahradíme její výskyty novými promìnnými $x_1, \ldots , x_k$
343 a pøidáme klauzule, které zabezpeèí, ¾e tyto promìnné budou v¾dy ohodnoceny stejnì:
345 (x_1 \Rightarrow x_2),
346 (x_2 \Rightarrow x_3),
347 (x_3 \Rightarrow x_4),
349 (x_{k-1} \Rightarrow x_k),
350 (x_k \Rightarrow x_1).
354 Mù¾eme dokonce zaøídit, aby se ka¾dý literál vyskytoval nejvý¹e dvakrát
355 (tedy ¾e ka¾dá promìnná se vyskytuje alespoò jednou pozitivnì a alespoò jednou negativnì).
356 Pokud by se nìjaká promìnná objevila ve~tøech stejných literálech, mù¾eme na~ni
357 také pou¾ít ná¹ trik a nahradit ji tøemi promìnnými. V~nových klauzulích se pak bude
358 vyskytovat jak pozitivnì, tak negativnì (opìt pøipomínáme, ¾e $a\Rightarrow b$
359 je jen zkratka za $\lnot a\lor b$).
363 \inp Tøi mno¾iny, napø. $K$ (kluci), $H$ (holky), $Z$ (zvíøátka) a
364 mno¾ina $T \subseteq K\times H\times Z$ kompatibilních trojic (tìch, kteøí se
367 \outp Zda existuje perfektní podmno¾ina trojic, tedy taková, v~ní¾ se ka¾dý
368 prvek mno¾in $K$, $H$ a~$Z$ úèastní právì jedné trojice.
370 \figure{3d_parovani.eps}{Ukázka 3D-párování}{3in}
372 \s{Pøevod 3,3-SATu na 3D-párování:}
373 Uva¾ujme trochu obecnìji. Pokud chceme ukázat, ¾e se na nìjaký problém dá pøevést
374 SAT, potøebujeme obvykle dvì vìci: Jednak konstrukci, která bude simulovat
375 promìnné, tedy nìco, co nabývá dvou stavù \<true>/\<false>. Pak také
376 potøebujeme cosi, co umí zaøídit, aby ka¾dá klauzule byla splnìna alespoò
377 jednou promìnnou. Jak to provést u~3D-párování?
379 Uva¾ujme následující konfiguraci:
383 \>V~ní se nacházejí 4~zvíøátka ($z_1$ a¾ $z_4$), 2~kluci ($k_1$ a $k_2$),
384 2~dívky ($d_1$ a $d_2$) a 4~trojice ($A$, $B$, $C$ a~$D$). Zatímco zvíøátka
385 se budou moci úèastnit i jiných trojic, kluky a dìvèata nikam jinam nezapojíme.
387 V¹imneme si, ¾e existují právì dvì mo¾nosti, jak tuto konfiguraci spárovat.
388 Abychom spárovali kluka $k_1$, tak musíme vybrat buï trojici~$A$ nebo~$B$.
389 Pokud si vybereme~$A$, $k_1$ i $d_2$ u¾ jsou spárovaní, tak¾e si nesmíme vybrat
390 $B$ ani~$D$. Pak jediná mo¾nost, jak spárovat $d_1$ a~$k_2$, je pou¾ít~$C$.
391 Naopak zaèneme-li trojicí~$B$, vylouèíme $A$ a~$D$ a pou¾ijeme~$D$ (situace
394 V¾dy si tedy musíme vybrat dvì protìj¹í trojice v~obrázku a druhé dvì nechat
395 nevyu¾ité. Tyto mo¾nosti budeme pou¾ívat k~reprezentaci promìnných. Pro ka¾dou
396 promìnnou si poøídíme jednu kopii obrázku. Volba $A+C$ bude odpovídat nule
397 a nespáruje zvíøátka $z_2$ a~$z_4$. Volba $B+D$ reprezentuje jednièku a nespáruje
398 $z_1$ a~$z_3$. Pøes tato nespárovaná zvíøátka mù¾eme pøedávat informaci o~hodnotì
399 promìnné do~klauzulí.
401 Zbývá vymyslet, jak reprezentovat klauzule. Mìjme klauzuli tvaru øeknìme
402 $(x \lor y \lor \lnot r)$. Potøebujeme zajistit, aby $x$ bylo
403 nastavené na $1$ nebo $y$ bylo nastavené na~$1$ nebo $r$ na $0$.
405 \fig{klauzule.eps}{4cm}
407 Pro takovouto klauzuli si poøídíme novou dvojici kluk a dívka, kteøí budou figurovat
408 ve~tøech trojicích se tøemi rùznými zvíøátky, co¾ budou volná zvíøátka
409 z~obrázkù pro pøíslu¹né promìnné. Zvolíme je tak, aby byla volná pøi správném
410 nastavení promìnné. Doká¾eme pøitom zaøídit, ¾e ka¾dé zvíøátko bude pou¾ité
411 v~maximálnì jedné klauzuli, nebo» ka¾dý literál se vyskytuje nejvý¹e dvakrát
412 a máme pro nìj dvì volná zvíøátka.
414 Je¹tì nám urèitì zbude $2p-k$ zvíøátek, kde $p$ je poèet promìnných a $k$
415 poèet klauzulí. Ka¾dá promìnná toti¾ dodá 2~volná zvíøátka a ka¾dá klauzule
416 pou¾ije jedno z~nich. Pøidáme proto je¹tì $2p-k$ párù lidí, kteøí milují úplnì
417 v¹echna zvíøátka; ti vytvoøí zbývající trojice.
419 Snadno ovìøíme, ¾e celý pøevod pracuje v~polynomiálním èase, rozmysleme si je¹tì,
422 Pokud formule byla splnitelná, z~ka¾dého splòujícího ohodnocení mù¾eme vyrobit
423 párování v~na¹í konstrukcí. Obrázek pro ka¾dou promìnnou spárujeme podle
424 ohodnocení (buï $A+C$ nebo $B+D$). Pro ka¾dou klauzuli si vybereme trojici,
425 která odpovídá nìkterému z~literálù, jimi¾ je klauzule splnìna.
427 A~opaènì: Kdy¾ nám nìkdo dá párovaní v~na¹í konstrukci, doká¾eme z~nìj
428 vyrobit splòující ohodnocení dané formule. Podíváme se, v~jakém stavu je
429 promìnná, a~to je v¹echno. Z~toho, ¾e jsou správnì spárované klauzule, u¾
430 okam¾itì víme, ¾e jsou v¹echny splnìné.
432 Ukázali jsme tedy, ¾e na 3D-párování lze pøevést 3,3-SAT, a~tedy i obecný SAT.
433 Pøevod v~opaèném smìru ponecháme jako cvièení, mù¾ete ho provést podobnì,
434 jako jsme na SAT pøevádìli nezávislou mno¾inu.
436 Jak je vidìt z~následujícího schématu, ukázali jsme, ¾e v¹echny problémy,
437 které jsme zkoumali, jsou navzájem pøevoditelné.
439 \figure{prevody.eps}{Problémy a pøevody mezi nimi}{3in}
441 \h{NP-úplné problémy}
443 V¹echny problémy, které jsme zatím zkoumali, mìly jednu spoleènou vlastnost.
444 ©lo v~nich toti¾ o~to, zda existuje nìjaký objekt. Napøíklad splòující ohodnocení
445 formule nebo klika v~grafu. Kdykoliv nám pøitom nìkdo takový objekt uká¾e,
446 umíme snadno ovìøit, ¾e má po¾adovanou vlastnost. Ov¹em najít ho u¾ tak
447 snadné není. Podobnì se chovají i mnohé dal¹í \uv{vyhledávací problémy},
448 pojïme se na nì tedy podívat obecnìji.
450 \s{Definice:} $\P$ je tøída\foot{Formálnì vzato je to mno¾ina, ale v~teorii slo¾itosti
451 se pro mno¾iny problémù v¾il název {\I tøídy.}}
452 rozhodovacích problémù, které jsou øe¹itelné v~polynomiálním èase. Jinak øeèeno, problém~$L$
453 le¾í v~$\P$ právì tehdy, kdy¾ existuje nìjaký algoritmus~$A$ a polynom~$f$
454 takové, ¾e pro ka¾dý vstup~$x$ algoritmus~$A$ dobìhne v~èase nejvý¹e $f(\vert x\vert)$
455 a vydá výsledek $A(x)=L(x)$.
457 Tøída $\P$ tedy zachycuje na¹i pøedstavu o~efektivnì øe¹itelných problémech.
458 Nyní definujeme tøídu~$\NP$, která bude odpovídat na¹i pøedstavì vyhledávacích
461 \s{Definice:} $\NP$ je tøída rozhodovacích problémù, v~ní¾ problém~$L$ le¾í právì
462 tehdy, pokud existuje nìjaký problém~$K\in\P$ a polynom~$g$, pøièem¾ pro ka¾dý
463 vstup~$x$ je $L(x)=1$ právì tehdy, pokud pro nìjaký øetìzec~$y$ délky nejvý¹e
464 $g(\vert y\vert)$ platí $K(x,y)=1$.%
465 \foot{Rozhodovací problémy mají na vstupu øetìzec bitù. Tak jaképak $x,y$?
466 Máme samozøejmì na~mysli nìjaké binární kódování této dvojice.}
468 Co to znamená? Algoritmus~$K$ øe¹í problém~$L$, ale kromì vstupu~$x$ má k~dispozici
469 je¹tì polynomiálnì dlouhou {\I nápovìdu~$y$.} Pøitom má platit, ¾e je-li $L(x)=1$,
470 musí existovat alespoò jedna nápovìda, kterou algoritmus~$K$ schválí. Pokud ov¹em
471 $L(x)=0$, nesmí ho pøesvìdèit ¾ádná nápovìda.
473 Jinými slovy~$y$ je jakýsi {\I certifikát,} který stvrzuje kladnou odpovìï,
474 a problém~$K$ má za úkol certifikáty kontrolovat. Pro kladnou odpovìï musí
475 existovat alespoò jeden schválený certifikát, pro zápornou musí být v¹echny
476 certifikáty odmítnuty.
478 \s{Pozorování:} Splnitelnost logických formulí je v~$\NP$. Staèí si toti¾ nechat napovìdìt, jak
479 ohodnotit jednotlivé promìnné, a pak ovìøit, je-li formule splnìna. Nápovìda je polynomiálnì
480 velká (dokonce lineárnì), splnìní zkontrolujeme také v~lineárním èase. Podobnì to mù¾eme to
481 dokázat i o~ostatních rozhodovacích problémech, se kterými jsme se zatím potkali.
483 \s{Pozorování:} Tøída $\P$ le¾í uvnitø $\NP$.
484 Pokud toti¾ problém umíme øe¹it v~polynomiálním èase bez nápovìdy, tak to zvládneme
485 v~polynomiálním èase i s~nápovìdou. Algoritmus~$K$ tedy bude ignorovat nápovìdy
486 a odpovìï spoèítá pøímo ze~vstupu.
488 \s{Otázka:} Jsou tøídy $\P$ a~$\NP$ rùzné? Na to se teoretiètí informatici sna¾í
489 odpovìdìt u¾ od 70. let minulého století a postupnì se z~toto stal asi vùbec nejslavnìj¹í
490 otevøený problém informatiky.
492 Napøíklad o~¾ádném z~na¹ich problémù nevíme, zda se nachází v~$\P$.
493 Brzy uvidíme, ¾e to jsou v~jistém smyslu nejtì¾¹í problémy v~$\NP$.
495 \s{Definice:} Problém $L$ nazveme $\NP$-{\I tì¾ký}, je-li na~nìj pøevoditelný
496 ka¾dý problém z~$\NP$. Pokud navíc $L\in\NP$, budeme øíkat, ¾e je $\NP$-{\I úplný.}
498 NP-úplné problémy jsou tedy nejtì¾¹ími problémy v~$\NP$, aspoò v~na¹em uspoøádání
501 \s{Lemma:} Pokud nìjaký $\NP$-tì¾ký problém~$L$ le¾í v~$\P$, pak $\P=\NP$.
504 Ji¾ víme, ¾e $\P\subseteq\NP$, tak¾e staèí dokázat opaènou nerovnost. Vezmìme
505 libovolný problém~$A\in\NP$. Z~úplnosti problému~$L$ víme, ¾e $A$ lze pøevést
506 na~$L$. Ov¹em problémy pøevoditelné na nìco z~$\P$ jsou samy také v~$\P$.
509 Z~definice $\NP$-úplnosti ale vùbec není jasné, ¾e nìjaký $\NP$-úplný problém doopravdy
510 existuje. Odpovìï je pøekvapivá:
512 \s{Vìta (Cookova):} SAT je $\NP$-úplný.
514 Dùkaz této vìty je znaènì technický a alespoò v~hrubých rysech ho pøedvedeme
515 v~závìru teto kapitoly. Jakmile ale máme jeden $\NP$-úplný problém, mù¾eme velice
516 snadno dokazovat i $\NP$-úplnost dal¹ích:
518 \s{Lemma:} Mìjme dva problémy $L,M\in\NP$. Pokud $L$ je $\NP$-úplný a $L\rightarrow M$,
519 pak $M$ je také $\NP$-úplný.
522 Jeliko¾ $M$ le¾í v~$\NP$, staèí o~nìm dokázat, ¾e je $\NP$-tì¾ký, tedy ¾e na nìj
523 lze pøevést libovolný problém z~$\NP$.
524 Uva¾me tedy nìjaký problém $Q\in\NP$. Jeliko¾ $L$ je~$\NP$-úplný, musí platit
525 $Q\rightarrow L$. Pøevoditelnost je ov¹em tranzitivní, tak¾e z~$Q\rightarrow L$
526 a $L\rightarrow M$ plyne $Q\rightarrow M$.
529 \s{Dùsledek:} Cokoliv, na co jsme umìli pøevést SAT, je také NP-úplné.
530 Napøíklad nezávislá mno¾ina, rùzné varianty SATu, klika v~grafu~\dots
532 \s{Dva mo¾né svìty:} Jestli je $\P=\NP$ nevíme a nejspí¹ je¹tì dlouho nebudeme
533 vìdìt. Nechme se ale na~chvíli uná¹et fantazií a zkusme si pøedstavit, jak by
534 vypadaly svìty, v~nich¾ platí jedna nebo druhá mo¾nost:
537 \:$\P=\NP$ -- to je na první pohled idylický svìt, v~nìm¾ jde ka¾dý vyhledávací
538 problém vyøe¹it v~polynomiálním èase, nejspí¹ tedy i prakticky efektivnì.
539 Má to i své stinné stránky: napøíklad jsme pøi¹li o~ve¹keré efektivní ¹ifrování
540 -- rozmyslete si, ¾e pokud umíme vypoèítat nìjakou funkci v~polynomiálním èase,
541 umíme efektivnì spoèítat i její inverzi.
542 \:$\P\ne\NP$ -- tehdy jsou $\P$ a $\NP$-úplné dvì disjunktní tøídy.
543 SAT a ostatní $\NP$-úplné problémy nejsou øe¹itelné v~polynomiálním
544 èase. Je ale stále mo¾né, ¾e aspoò na nìkteré z~nich existují prakticky pou¾itelné algoritmy,
545 tøeba o~slo¾itosti $\Theta((1+\varepsilon)^n)$ nebo $\Theta(n^{\log n/100})$.
546 Ví se, ¾e tøída $\NP$ by pak obsahovala i problémy, které le¾í \uv{mezi}
547 $\P$ a $\NP$-úplnými.
550 \h{Katalog NP-úplných problémù}
552 Pokud se setkáme s~problémem, který neumíme zaøadit do~$\P$, hodí se vyzkou¹et,
553 zda je $\NP$-úplný. K~tomu se hodí mít alespoò základní zásobu \uv{uèebnicových}
554 $\NP$-úplných problémù, abychom si mohli vybrat, z~èeho pøevádìt. Uká¾eme tedy
555 katalog nìkolika nejbì¾nìj¹ích $\NP$-úplných problémù. O~nìkterých jsme to
556 dokázali bìhem této kapitoly, u~ostatních alespoò naznaèíme, jak na nì.
558 \s{Standardní NP-úplné problémy:}
562 \:SAT (splnitelnost logických formulí v~CNF)
563 \:3-SAT (ka¾dá klauzule obsahuje max.~3 literály)
564 \:3,3-SAT (a navíc ka¾dá promìnná se vyskytuje nejvý¹e~$3\times$)
565 \:SAT pro obecné formule (nejen CNF; uká¾eme ní¾e)
566 \:Obvodový SAT (místo formule booleovský obvod; viz ní¾e)
570 \:Nezávislá mno¾ina (existuje mno¾ina alespoò~$k$ vrcholù taková, ¾e ¾ádné dva nejsou propojeny hranou?)
571 \:Klika (existuje úplný podgraf na~$k$ vrcholech?)
572 \: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 právì jednou?)
573 \:Barvení grafu (lze obarvit vrcholy $k$~barvami tak, aby vrcholy stejné barvy nebyly nikdy spojeny hranou? $\NP$-úplné u¾ pro~$k=3$)
574 \:Hamiltonovská cesta (cesta obsahující v¹echny vrcholy)
575 \:Hamiltonovská kru¾nice (opìt obsahuje v¹echny vrcholy)
579 \:Batoh (nejjednodu¹¹í verze: má daná mno¾ina èísel podmno¾inu s~daným souètem?)
580 \:Batoh -- optimalizace (podobnì jako u pøedchozího problému, ale místo mno¾iny èísel máme mno¾inu
581 pøedmìtù s~vahami a cenami, chceme co nejdra¾¹í podmno¾inu, její¾ váha nepøesáhne zadanou kapacitu
583 \:Dva loupe¾níci (lze rozdìlit danou mno¾inu èísel na~dvì podmno¾iny se stejným souètem?)
584 \:${\bf Ax}={\bf b}$ (soustava celoèíselných lineárních rovnic; je dána matice~${\bf A}\in\{0,1\}^{m\times n}$
585 a vektor~${\bf b}\in\{0,1\}^m$, existuje vektor~${\bf x}\in\{0,1\}^n$ takový, ¾e ${\bf Ax}={\bf b}$?)
589 \h{Náznak dùkazu Cookovy vìty}
591 Zbývá dokázat Cookovu vìtu. Technické detaily si odpustíme, ale aspoò naèrtneme
592 základní my¹lenku dùkazu.
594 Potøebujeme tedy dokázat, ¾e SAT je $\NP$-úplný, a to z~definice. Uká¾eme to
595 ale nejprve pro jiný problém, pro takzvaný {\I obvodový SAT.} V~nìm máme na
596 vstupu booleovský obvod (hradlovou sí») s~jedním výstupem a ptáme se, zda
597 jí mù¾eme pøivést na vstupy takové hodnoty, aby vydala výsledek~1.
599 To je obecnìj¹í ne¾ SAT pro formule (dokonce i neomezíme-li formule na CNF),
600 proto¾e ka¾dou formuli mù¾eme pøelo¾it na lineárnì velký obvod. (Platí i opaènì,
601 ¾e ka¾dému obvodu s~jedním výstupem mù¾eme pøiøadit ekvivalentní formuli,
602 ale ta mù¾e být a¾ exponenciálnì velká.)
604 Nejprve tedy doká¾eme $\NP$-úplnost obvodového SATu a~pak ho pøevedeme na
605 obyèejný SAT v~CNF. Tím bude dùkaz Cookovy vìty hotový. Zaènìme lemmatem,
606 v~nìm¾ bude koncentrováno v¹e technické.
608 \s{Lemma:} Nech» $L$ je problém le¾ící v~$\P$. Potom existuje polynom~$p$ a algoritmus,
609 který pro ka¾dé~$n$ sestrojí v~èase $p(n)$ hradlovou sí» $B_n$ s~$n$~vstupy
610 a jedním výstupem, která øe¹í~$L$. Tedy pro v¹echny øetìzce~$x$ musí platit
614 Náznakem. Na základì zku¹eností z Principù poèítaèù intuitivnì chápeme poèítaèe
615 jako nìjaké slo¾ité booleovské obvody, jejich¾ stav se mìní v~èase. Uva¾me tedy
616 nìjaký problém $L \in \P$ a polynomiální algoritmus, který ho øe¹í. Pro vstup
617 velikosti~$n$ algoritmus dobìhne v~èase~$T$ polynomiálním v~$n$ a spotøebuje $\O(T)$ bunìk pamìti.
618 Staèí nám tedy \uv{poèítaè s~pamìtí velkou $\O(T)$}, co¾ je nìjaký booleovský obvod
619 velikosti polynomiální v~$T$, a~tedy i v~$n$. Vývoj v~èase o¹etøíme tak, ¾e sestrojíme~$T$
620 kopií tohoto obvodu, ka¾dá z~nich bude odpovídat jednomu kroku výpoètu a bude
621 propojena s~\uv{minulou} a \uv{budoucí} kopií. Tím sestrojíme booleovský obvod,
622 který bude øe¹it problém~$L$ pro vstupy velikosti~$n$ a bude polynomiálnì velký
625 \s{Ekvivalentní definice~$\NP$:}
626 Pro dùkaz následující vìty si dovolíme drobnou úpravu v~definici tøídy $\NP$.
627 Budeme chtít, aby nápovìda
628 mìla pevnou velikost, závislou pouze na~velikosti vstupu (tedy: $\vert y \vert
629 = g(\vert x \vert)$ namísto $\vert y \vert \le g(\vert x \vert)$). Proè je taková
630 úprava bez újmy na obecnosti? Staèí pùvodní nápovìdu doplnit na po¾adovanou délku
631 nìjakými \uv{mezerami}, které budeme pøi ovìøování nápovìdy ignorovat.
633 \s{Vìta:} Obvodový SAT je $\NP$-úplný.
636 Obvodový SAT evidentnì le¾í v~$\NP$ -- staèí si nechat poradit vstup, sí»
637 topologicky setøídit a v~tomto poøadí poèítat hodnoty hradel.
639 Mìjme nyní nìjaký problém $L$ z~$\NP$, o~nìm¾ chceme dokázat, ¾e se dá pøevést
640 na~obvodový SAT. Kdy¾ nám nìkdo pøedlo¾í nìjaký vstup~$x$ délky~$n$,
641 spoèítáme velikost nápovìdy $g(n)$. Víme, ¾e algoritmus~$K$, který kontroluje,
642 zda nápovìda je správnì, je v~$\P$. Vyu¾ijeme pøedchozí lemma, abychom získali obvod,
643 který pro konkrétní velikost vstupu~$n$ poèítá to, co kontrolní algoritmus~$K$.
644 Vstupem tohoto obvodu bude~$x$ (vstup problému~$L$) a~nápovìda~$y$. Na výstupu se
645 dozvíme, zda je nápovìda správná. Velikost tohoto obvodu bude èinit $p(g(n))$,
648 \fig{kobvod.eps}{2.3cm}
650 V tomto obvodu zafixujeme vstup $x$ (na místa vstupu dosadíme konkrétní hodnoty
651 z $x$). Tím získáme obvod, jeho¾ vstup je jen~$y$, a~chceme zjistit, zda za~$y$
652 mù¾eme dosadit nìjaké hodnoty tak, aby na výstupu bylo \<true>. Jinými slovy,
653 ptáme se, zda je tento obvod splnitelný.
655 Ukázali jsme tedy, ¾e pro libovolný problém z~$\NP$ doká¾eme sestrojit funkci,
656 která pro ka¾dý vstup~$x$ v~polynomiálním èase vytvoøí obvod, jen¾ je splnitelný
657 pravì tehdy, kdy¾ odpovìï tohoto problému na vstup~$x$ má být kladná. To je pøesnì
658 pøevod z~daného problému na obvodový SAT.
661 \s{Lemma:} Obvodový SAT se dá pøevést na 3-SAT.
664 Budeme postupnì budovat formuli v~konjunktivní normální formì. Ka¾dý booleovský
665 obvod se dá v~polynomiálním èase pøevést na~ekvivalentní obvod, ve~kterém se
666 vyskytují jen hradla {\csc and} a {\csc not}, tak¾e staèí najít klauzule
667 odpovídající tìmto hradlùm. Pro ka¾dé hradlo v~obvodu zavedeme novou promìnnou
668 popisující jeho výstup. Pøidáme klauzule, které nám kontrolují, ¾e toto hradlo
669 máme ohodnocené konzistentnì.
671 {\I Pøevod hradla \csc not}: Na vstupu hradla budeme mít nìjakou promìnnou $x$
672 (která pøi¹la buïto pøímo ze~vstupu celého obvodu, nebo je to promìnná,
673 která vznikla na výstupu nìjakého hradla) a na výstupu promìnnou $y$. Pøidáme
674 klauzule, které nám zaruèí, ¾e jedna promìnná bude negací té druhé:
675 $$\matrix{ (x \lor y), \cr
676 (\neg{x} \lor \neg{y}). \cr }
678 \vcenter{\hbox{\epsfxsize=0.7cm\epsfbox{not.eps}}}
681 {\I Pøevod hradla \csc and}: Hradlo má vstupy $x, y$ a~výstup $z$. Potøebujeme
682 pøidat klauzule, které nám popisují, jak se má hradlo {\csc and} chovat. Tyto
683 vztahy pøepí¹eme do~konjunktivní normální formy:
686 x\ \&\ y \Rightarrow z \cr
687 \neg{x} \Rightarrow \neg{z} \cr
688 \neg{y} \Rightarrow \neg{z} \cr
694 (z \lor \neg{x} \lor \neg{y}) \cr
699 \vcenter{\hbox{\epsfxsize=0.7cm\epsfbox{and.eps}}}
702 Tím v~polynomiálním èase vytvoøíme formuli, která je splnitelná právì tehdy,
703 je-li splnitelný zadaný obvod. Ve~splòujícím ohodnocení formule bude obsa¾eno
704 jak splòující ohodnocení obvodu, tak výstupy v¹ech hradel obvodu.
708 Tím jsme také odpovìdìli na otázku, kterou jsme si kladli pøi zavádìní SATu,
709 tedy zda omezením na CNF o~nìco pøijdeme. Teï u¾ víme, ¾e nepøijdeme -- libovolná
710 booleovská formule se dá pøímoèaøe pøevést na obvod a ten zase na formuli
711 v~CNF. Zavádíme sice nové promìnné, ale nová formule je splnitelná právì
712 tehdy, kdy ta pùvodní.
projects / ads2.git / blob