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 V¹echny úlohy, které jsme zatím potkali, jsme umìli vyøe¹it algoritmem
10 s~polynomiální èasovou slo¾itostí. V~prvním pøiblí¾ení mù¾eme øíci, ¾e
11 polynomialita docela dobøe vystihuje praktickou pou¾itelnost algoritmu.%
12 \foot{Jistì vás napadne spousta protipøíkladù, jako tøeba algoritmus se
13 slo¾itostí $\O(1.001^n)$, který nejspí¹ je pou¾itelný, aèkoliv není polynomiální,
14 a~jiný se slo¾itostí $\O(n^{100})$, u~kterého je tomu naopak. V¹ak jsme
15 øíkali, ¾e nám jde o~první pøiblí¾ení, které navíc u~vìt¹iny problémù
16 funguje pøekvapivì dobøe.}
18 Existují tedy polynomiální algoritmy pro v¹echny úlohy? Zajisté ne,
19 jsou dokonce i takové úlohy, je¾ ¾ádným algoritmem vyøe¹it nelze.
20 Ale i mezi tìmi algoritmicky øe¹itelnými potkáme spoustu úloh,
21 pro které zatím ¾ádný polynomiální algoritmus není známý (ale ani neumíme
22 dokázat, ¾e neexistuje). Takové úlohy jsou pøekvapivì èasté, proto se
23 na této pøedná¹ce podíváme na nìkolik typických pøíkladù.
25 Navíc uvidíme, ¾e aèkoliv tyto úlohy neumíme efektivnì øe¹it, lze mezi
26 nimi nalézt zajímavé vztahy a pomocí tìchto vztahù obtí¾nost problémù
27 vzájemnì porovnávat. Z~tìchto úvah vyrùstá i skuteèná teorie slo¾itosti
28 se svými hierarchiemi slo¾itostních tøíd. Mù¾ete tedy následující kapitolu
29 pova¾ovat za malou ochutnávku toho, jak lze k~tøídám problémù pøistupovat.
31 \h{Rozhodovací problémy a pøevody mezi nimi}
33 Aby se nám teorie pøíli¹ nerozko¹atila, omezíme své úvahy na rozhodovací
34 problémy. To jsou úlohy, jejich¾ výstupem je jediný bit -- máme tedy rozhodnout,
35 zda vstup má èi nemá urèenou vlastnost. Vstup pøitom budeme reprezentovat øetìzcem
36 nul a jednièek -- libovolnou jinou \uv{rozumnou} reprezentaci doká¾eme na tyto
37 øetìzce pøevést v~polynomiálním èase. Formálnìji:
39 \s{Definice:} {\I Rozhodovací problém} (zkrácenì {\I problém}) je funkce z~mno¾iny $\{0,1\}^*$ v¹ech
40 øetìzcù nad binární abecedou do mno¾iny $\{0,1\}$.%
41 \foot{Ekvivalentnì bychom se na~problém mohli také dívat jako na nìjakou
42 mno¾inu $A\subseteq \{0,1\}^*$ vstupù, na nì¾ je odpovìï~1. Tento pøístup
43 mají rádi v~teorii automatù.}
45 \s{Pøíklad:} Je dán bipartitní graf $G$ a $k \in {\bb N}$ (respektive nìjaké
46 jejich kódování øetìzci bitù). Existuje v $G$ párování, které obsahuje alespoò $k$
47 hran? (Také bychom se mohli ptát, zda existuje párování o~právì~$k$ hranách,
48 co¾ je toté¾, nebo» pøebyteèné hrany mù¾eme prostì odstranit.)
50 \s{Odboèka:} Ve~vìt¹inì pøípadù bychom chtìli nejen zjistit, jestli takové
51 párování existuje, ale také nìjaké konkrétní najít. Obvykle ale bývá snadné
52 pomocí rozhodovací verze problému hledaný objekt sestrojit. Uka¾me si, jak
55 Mìjme èernou skøíòku (fungující v polynomiálním èase), která odpoví, zda daný
56 graf má nebo nemá párování o~$k$ hranách. Odebereme z~grafu libovolnou hranu
57 a zeptáme se, jestli i tento nový graf má párovaní velikosti~$k$. Kdy¾ má, pak tato
58 hrana nebyla pro existenci párování potøebná, a~tak ji odstraníme. Kdy¾ naopak
59 nemá (hrana patøí do ka¾dého párování po¾adované velikosti), tak si danou hranu
60 poznamenáme a odebereme nejen ji a její vrcholy, ale také hrany, které do tìchto
61 vrcholù vedly. Toto je korektní krok, proto¾e v pùvodním grafu tyto vrcholy
62 byly navzájem spárované, a tedy nemohou být spárované s~¾ádnými jinými vrcholy.
63 Na~nový graf aplikujeme znovu tentý¾ postup. Výsledkem je mno¾ina hran, které patøí
64 do hledaného párování. Hran, a tedy i iterací na¹eho algoritmu, je polynomiálnì
65 mnoho a skøíòka funguje v polynomiálním èase, tak¾e celý algoritmus je polynomiální.%
66 \foot{Zde se skrývá hlavní dùvod, proè informatici mají tak rádi polynomiální
67 algoritmy. Tøída v¹ech polynomù je toti¾ nejmen¹í tøídou funkcí, která obsahuje
68 v¹echny \uv{základní} funkce (konstanty, $n$, $n^2$) a je uzavøená na sèítání,
69 odèítání, násobení i skládání funkcí.}
71 \s{Zpìt z~odboèky:} Jak párovací problém vyøe¹it? Vìrni matfyzáckým vtipùm,
72 pøevedeme ho na nìjaký, který u¾ vyøe¹it umíme. To u¾ ostatnì umíme -- na~toky
73 v~sítích. Poka¾dé, kdy¾ se ptáme na existenci párování velikosti alespoò~$k$
74 v~nìjakém bipartitním grafu, umíme efektivnì sestrojit nìjakou sí» a zeptat se,
75 zda v~této síti existuje tok velikosti alespoò~$k$. Chceme tedy pøelo¾it vstup
76 jednoho problému na vstup jiného problému tak, aby odpovìï zùstala stejná.
78 Takovéto pøevody mezi problémy mù¾eme definovat i~obecnìji:
80 \s{Definice:} Jsou-li $A$, $B$ rozhodovací problémy, øíkáme, ¾e $A$ lze {\I
81 pøevést} (neboli {\I redukovat}) na~$B$ (pí¹eme $A \rightarrow B$) právì tehdy,
82 kdy¾ existuje funkce $f: \{0,1\}^* \rightarrow \{0,1\}^*$, spoèitatelná v~polynomiálním
83 èase, taková, ¾e pro $\forall x\in \{0,1\}^*: A(x) = B(f(x))$.
85 \s{Pozorování:} $A\rightarrow B$ také znamená, ¾e problém~$B$ je alespoò tak tì¾ký
86 jako problém~$A$. Tím myslíme, ¾e kdykoliv umíme øe¹it~$B$, je vyøe¹it~$A$ nejvý¹e
87 polynomiálnì obtí¾nìj¹í. Speciálnì platí:
89 \s{Lemma:} Pokud $A\rightarrow B$ a $B$~lze øe¹it v~polynomiálním èase,
90 pak i~$A$ lze øe¹it v~polynomiálním èase.
93 Nech» existuje algoritmus øe¹ící problém~$B$ v~èase $\O(b^k)$, kde $b$~je
94 délka vstupu tohoto problému a $k$~konstanta. Mìjme dále funkci~$f$ pøevádìjící
95 $A$ na~$B$ v~èase $\O(a^\ell)$ pro vstup délky~$a$. Chceme-li nyní spoèítat
96 $A(x)$ pro nìjaký vstup~$x$ délky~$a$, spoèítáme nejprve $f(x)$. To bude trvat
97 $\O(a^\ell)$ a vyjde výstup délky takté¾ $\O(a^\ell)$ -- del¹í v~daném èase
98 funkce~$f$ nestihne vypsat. Tento vstup pak pøedáme algoritmu pro problém~$B$,
99 který nad ním stráví èas $\O((a^\ell)^k) = \O(a^{k\ell})$, co¾ je polynom
100 v~délce pùvodního vstupu.
103 \s{Pozorování:} O~relaci pøevoditelnosti na mno¾inì v¹ech problémù platí:
105 \:{\I Je reflexivní} ($A\rightarrow A$) -- úlohu mù¾eme pøevést na tuté¾ identickým zobrazením.
106 \:{\I Je tranzitivní} ($A\rightarrow B \land B\rightarrow C \Rightarrow A\rightarrow C$) --
107 pokud funkce~$f$ pøevádí $A$ na~$B$ a funkce~$g$ pøevádí $B$ na~$C$, pak funkce $g\circ f$
108 pøevádí $A$ na~$C$. Slo¾ení dvou polynomiálnì vyèíslitelných funkcí je zase polynomiálnì
109 vyèíslitelná funkce, jak u¾ jsme zpozorovali v~dùkazu pøedchozího lemmatu.
110 \:{\I Není antisymetrická} -- napøíklad problémy \uv{na vstupu je øetìzec zaèínající nulou}
111 a \uv{na vstupu je øetìzec konèící nulou} lze mezi sebou pøevádìt obìma smìry.
112 \:Existují {\I navzájem nepøevoditelné problémy} -- tøeba pro problémy $A(x)=0$ a $B(y)=1$
113 nemù¾e existovat pøevod ani jedním smìrem.
116 \>Relacím, které jsou reflexivní a tranzitivní, ale obecnì nesplòují antisymetrii,
117 se øíká {\I kvaziuspoøádání}. Pøevoditelnost je tedy èásteèné kvaziuspoøádání na mno¾inì
118 v¹ech problémù.\foot{Kdybychom z~nìj chtìli vyrobit opravdové (by» èásteèné) uspoøádání,
119 mohli bychom definovat ekvivalenci $A\sim B \equiv A\rightarrow B \land B\rightarrow A$
120 a relaci pøevoditelnosti zavést jen na tøídách této ekvivalence. Taková pøevoditelnosti
121 by u¾ byla slabì antisymetrická. To je v~matematice dost bì¾ný trik, øíká se mu {\I faktorizace} kvaziuspoøádání.}
123 Nyní se ji¾ podíváme na pøíklady nìkolika problémù, které se obecnì pova¾ují
124 za tì¾ké. Uvidíme, ¾e ka¾dý z~nich je mo¾né pøevést na v¹echny ostatní, tak¾e
125 z~na¹eho \uv{polynomiálního} pohledu jsou stejnì obtí¾né.
127 \prob{SAT -- Splnitelnost logických formulí v~CNF}
129 Splnitelnost (satisfiability) spoèívá v~tom, ¾e dostaneme logickou formuli
130 s~promìnnými a logickými spojkami a ptáme se, zda lze za promìnné dosadit
131 0 a~1 tak, aby formule dala výsledek 1 (byla splnìna).
133 Zamìøíme se na speciální formu zadání formulí, takzvanou {\I konjunktivní normální
137 \:{\I formule} je slo¾ena z~jednotlivých {\I klauzulí} oddìlených spojkou~$\land$,
138 \:ka¾dá {\I klauzule} je slo¾ená z {\I literálù} oddìlených $\lor$,
139 \:ka¾dý {\I literál} je buïto promìnná nebo její negace.
141 \>Formule mají tedy tvar
142 $$\psi = (\ldots\lor\ldots\lor\ldots\lor\ldots) \land (\ldots\lor\ldots\lor\ldots\lor\ldots) \land \ldots $$
144 \inp Formule $\psi$ v konjunktivní normální formì.
146 \outp Existuje-li dosazení 0 a~1 za promìnné tak, aby $\psi(\ldots) = 1$.
148 \s{Poznámka:} Co kdybychom chtìli zjistit, zda je splnitelná nìjaká formule,
149 která není v~CNF? V~logice se dokazuje, ¾e ke~ka¾dé formuli lze najít ekvivalentní
150 formuli v~CNF, ale pøi tom se bohu¾el formule mù¾e a¾ exponenciálnì prodlou¾it.
151 Pozdìji uká¾eme, ¾e pro ka¾dou formuli~$\chi$ existuje nìjaká formule $\chi'$ v~CNF,
152 která je splnitelná právì tehdy, kdy¾ je $\chi$ splnitelná. Formule $\chi'$ pøitom
153 bude dlouhá $\O(\vert\chi\vert)$, ale budou v~ní nìjaké nové promìnné.
155 \prob{3-SAT -- Splnitelnost formulí s~krátkými klauzulemi}
157 Uva¾ujme variantu SATu, ve~které mno¾inu mo¾ných formulí je¹tì omezíme.
158 Povolíme na vstupu pouze takové formule v~CNF, jejich¾ ka¾dá klauzule obsahuje
159 nejvý¹e tøi literály. Uká¾eme, ¾e tento problém je stejnì tì¾ký jako pùvodní SAT.
161 \s{Pøevod 3-SATu na SAT:}
162 Jeliko¾ 3-SAT je speciálním pøípadem SATu, poslou¾í tu jako pøevodní funkce
165 \s{Pøevod SATu na 3-SAT:}
166 Nech» se ve~formuli vyskytuje nìjaká \uv{¹patná} klauzule o~$k>3$ literálech.
167 Mù¾eme ji zapsat ve~tvaru $(\alpha\lor\beta)$, kde $\alpha$ obsahuje 2~literály
168 a $\beta$ $k-2$ literálù. Poøídíme si novou promìnnou~$x$ a klauzuli nahradíme
169 dvìma novými $(\alpha\lor x)$ a $(\beta\lor\lnot x)$. První z~nich obsahuje 3~literály,
170 tedy je dobrá. Druhá má $k-1$ literálù, tak¾e sice mù¾e být ¹patná, ale aspoò je
171 krat¹í, tak¾e mù¾eme postup opakovat.
173 Takto postupnì nahradíme v¹echny ¹patné klauzule dobrými, co¾ bude trvat nejvý¹e
174 polynomiálnì dlouho: klauzuli délky~$k$ rozbijeme po $k-3$ krocích, ¹patných
175 klauzulí je jistì polynomiálnì s~délkou formule. Staèí ukázat, ¾e ka¾dý jednotlivý
176 krok zachovává splnitelnost formule.
178 Pokud pùvodní formule byla splnitelná, uva¾me nìjaké splòující ohodnocení promìnných.
179 Uká¾eme, ¾e v¾dy mù¾eme novou promìnnou~$x$ nastavit tak, aby vzniklo splòující
180 ohodnocení nové formule. Víme, ¾e klauzule $(\alpha\lor\beta)$ byla splnìna. Proto
183 \:Buïto $\alpha=1$. Pak polo¾íme $x=0$, tak¾e $(\alpha\lor x)$ bude splnìno díky~$\alpha$
184 a $(\beta\lor\lnot x)$ díky~$x$.
185 \:Anebo $\alpha=0$. Pak polo¾íme $x=1$, tak¾e $(\alpha\lor x)$ bude splnìno díky~$x$,
186 zatímco $(\beta\lor\lnot x)$ díky~$\beta$.
188 \>Splnìnost ostatních klauzulí na¹e transformace nijak neovlivnila.
190 A~naopak: pokud dostaneme splòující ohodnocení nové formule, umíme z~nìj získat
191 splòující ohodnocení formule pùvodní. Uká¾eme, ¾e staèí zapomenout promìnnou~$x$.
192 V¹echny klauzule, kterých se na¹e transformace netýká, jsou nadále splnìné.
193 Co klauzule $(\alpha\lor\beta)$?
195 \:Buïto $x=0$, pak musí být $(\alpha\lor x)$ splnìna díky~$\alpha$, tak¾e
196 $(\alpha\lor\beta)$ je také splnìna díky~$\alpha$.
197 \:Anebo $x=1$, pak musí být $(\beta\lor\lnot x)$ splnìna díky~$\beta$, tak¾e
198 i $(\alpha\lor\beta)$ je splnìna.
201 \>Tím je pøevod hotov, SAT a 3-SAT jsou tedy ekvivalentní.
203 \prob{NzMna -- Nezávislá mno¾ina vrcholù v~grafu}
205 \s{Definice:} Mno¾ina vrcholù grafu je {\I nezávislá,} pokud ¾ádné dva
206 vrcholy le¾ící v~této mno¾inì nejsou spojeny hranou. (Jinými slovy pokud
207 tato mno¾ina indukuje podgraf bez hran.)
209 \figure{nezmna.eps}{Pøíklad nezávislé mno¾iny}{0.7in}
211 \>Na samotnou existenci nezávislé mno¾iny se nemá smysl ptát -- prázdná mno¾ina
212 èi libovolný jeden vrchol jsou v¾dy nezávislé. Zajímavé ale je, jestli má graf
213 dostateènì velkou nezávislou mno¾inu.
215 \inp Neorientovaný graf $G$ a èíslo $k \in {\bb N}$.
217 \outp Zda existuje nezávislá mno¾ina $A \subseteq V(G)$ velikosti alespoò~$k$.
219 \s{Pøevod 3-SAT $\rightarrow$ NzMna:}
220 My¹lenka pøevodu bude jednoduchá: z~ka¾dé klauzule budeme chtít vybrat jeden
221 literál, jeho¾ nastavením klauzuli splníme. Samozøejmì si musíme dát pozor, abychom
222 v~rùzných klauzulích nevybírali konfliktnì, tj. jednou~$x$ a podruhé~$\lnot x$.
224 Jak to pøesnì zaøídit:
225 pro ka¾dou z~$k$~klauzulí zadané formule vytvoøíme trojúhelník a ka¾dému z~jeho
226 vrcholù pøiøadíme jeden z~literálù pøíslu¹né klauzule. (Pokud by klauzule obsahovala
227 ménì literálù, prostì nìkteré vrcholy trojúhelníka vynecháme.) Navíc spojíme
228 hranami v¹echny dvojice konfliktních literálù ($x$ a~$\lnot x$).
230 V~tomto grafu se budeme ptát po nezávislé mno¾inì velikosti alespoò~$k$.
231 Jeliko¾ z~ka¾dého trojúhelníka mù¾eme do~nezávislé mno¾iny vybrat nejvý¹e jeden vrchol,
232 jediná mo¾nost, jak splnit po¾adovanou velikost, je vybrat z~ka¾dého právì jeden
233 vrchol. Uká¾eme, ¾e taková nezávislá mno¾ina existuje právì tehdy, je-li formule splnitelná.
235 Máme-li splòující ohodnocení formule, mù¾eme z~ka¾dé klauzule vybrat jeden splnìný
236 literál. Do nezávislé mno¾iny umístíme vrcholy odpovídající tìmto literálùm. Je jich
237 právì~$k$. Jeliko¾ ka¾dé dva vybrané vrcholy le¾í v~rùzných trojúhelnících a nikdy
238 nemù¾e být splnìný souèasnì literál a jeho negace, mno¾ina je opravdu nezávislá.
240 A~opaènì: Kdykoliv dostaneme nezávislou mno¾inu velikosti~$k$, vybereme literály
241 odpovídající vybraným vrcholùm a pøíslu¹né promìnné nastavíme tak, abychom tyto
242 literály splnili. Díky hranám mezi konfliktními literály se nikdy nestane, ¾e bychom
243 potøebovali souèasnì splnit literál a jeho negaci. Zbývající promìnné nastavíme
244 libovolnì. Jeliko¾ jsme v~ka¾dé klauzuli splnili alespoò jeden literál, jsou
245 splnìny v¹echny klauzule, a~tedy i celá formule.
247 Pøevod je tedy korektní, zbývá rozmyslet, ¾e bì¾í v~polynomiálním èase:
248 Poèet vrcholù grafu odpovídá poètu literálù ve formuli, poèet hran je maximálnì
249 kvadratický, tak¾e celý pøevod je polynomiální.
251 \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}
253 \s{Pøevod NzMna $\rightarrow$ SAT:}
255 Vrcholy grafu oèíslujeme od~1 do~$n$ a poøídíme si pro nì promìnné $v_1, \ldots, v_n$,
256 které budou indikovat, zda byl pøíslu¹ný vrchol vybrán do nezávislé mno¾iny
257 (pøíslu¹né ohodnocení promìnných tedy bude odpovídat charakteristické funkci nezávislé mno¾iny).
259 Aby mno¾ina byla opravdu nezávislá, pro ka¾dou hranu $ij \in E(G)$ pøidáme klauzuli
260 $(\lnot v_i \lor \lnot v_j)$.
262 Je¹tì potøebujeme zkontrolovat, ¾e mno¾ina je dostateènì velká. To neumíme provést
263 pøímo, ale pou¾ijeme lest: vyrobíme matici $X$ tvaru~$k\times n$, která bude popisovat
264 oèíslování vrcholù nezávislé mno¾iny èísly od~1 do~$k$. Konkrétnì $x_{ij}$ bude øíkat,
265 ¾e v~poøadí $i$-tý prvek nezávislé mno¾iny je vrchol~$j$. K~tomu potøebujeme zaøídit:
268 \:Aby v~ka¾dém sloupci byla nejvý¹e jedna jednièka. Na to si poøídíme klauzule
269 $(x_{i,j} \Rightarrow \lnot x_{i',j})$ pro $1\le i<i'\le k$, $1\le j\le n$.
270 (Jsou to implikace, ale mù¾eme je zapsat i jako disjunkce, proto¾e $a\Rightarrow b$
271 je toté¾ jako $\lnot a \lor b$.)
272 \:Aby v~ka¾dém øádku le¾ela právì jedna jednièka. Nejprve zajistíme nejvý¹e jednu
273 klauzulemi $(x_{i,j} \Rightarrow \lnot x_{i,j'})$ pro $1\le i\le k$, $1\le j<j'\le n$.
274 Pak pøidáme klauzule $(x_{i,1}\lor x_{i,2}\lor \ldots \lor x_{i,n})$ pro $1\le i\le k$,
275 které po¾adují alespoò jednu jednièku v~øádku.
276 \:Vztah mezi oèíslováním a nezávislou mno¾inou: pøidáme klauzule $x_{i,j} \Rightarrow v_j$
277 pro $1\le i\le k$, $1\le j\le n$. (V¹imnìte si, ¾e nezávislá mno¾ina mù¾e obsahovat
278 i neoèíslované prvky, ale to nám nevadí. Dùle¾ité je, aby mìla $k$~oèíslovaných.)
281 Tím jsme vytvoøili polynomiálnì velkou formuli, která je splnitelná právì tehdy,
282 kdy¾ v~zadaném grafu existuje nezávislá mno¾ina o~alespoò~$k$ prvcích.
284 \prob{Klika -- úplný podgraf}
286 Podobnì jako nezávislou mno¾inu mù¾eme v~grafu hledat i {\I kliku} -- úplný
287 podgraf dané velikosti.
289 \inp Graf $G$ a èíslo $k \in N$.
291 \outp Existuje-li úplný podgraf grafu $G$ na alespoò $k$ vrcholech.
293 \figure{klika.eps}{Pøíklad kliky}{2in}
295 Tento problém je ekvivalentní s~hledáním nezávislé mno¾iny. Pokud v~grafu prohodíme
296 hrany a nehrany, stane se z~ka¾dé kliky a nezávislá mno¾ina a naopak. Pøevodní funkce
297 tedy zneguje hrany a ponechá èíslo~$k$.
299 \figure{doplnek_nm.eps}{Prohození hran a nehran}{2in}
301 \prob{3,3-SAT -- splnitelnost s~malým poètem výskytù}
303 Ji¾ jsme ukázali, ¾e SAT zùstane stejnì tì¾ký, omezíme-li se na formule
304 s~klauzulemi délky nejvý¹e~3. Mù¾eme ho dokonce omezit je¹tì více: budeme
305 navíc po¾adovat, aby se ka¾dá promìnná vyskytovala v~maximálnì tøech literálech.
306 Tomuto problému se øíká 3,3-SAT.
308 \s{Pøevod 3-SATu na 3,3-SAT:}
309 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$
310 a pøidáme klauzule, které zabezpeèí, ¾e tyto promìnné budou v¾dy ohodnoceny stejnì:
312 (x_1 \Rightarrow x_2),
313 (x_2 \Rightarrow x_3),
314 (x_3 \Rightarrow x_4),
316 (x_{k-1} \Rightarrow x_k),
317 (x_k \Rightarrow x_1).
321 Mù¾eme dokonce zaøídit, aby se ka¾dý literál vyskytoval nejvý¹e dvakrát
322 (tedy ¾e ka¾dá promìnná se vyskytuje alespoò jednou pozitivnì a alespoò jednou negativnì).
323 Pokud by se nìjaká promìnná objevila ve~tøech stejných literálech, mù¾eme na~ni
324 také pou¾ít ná¹ trik a nahradit ji tøemi promìnnými. V~nových klauzulích se pak bude
325 vyskytovat jak pozitivnì, tak negativnì.
329 \inp Tøi mno¾iny, napø. $K$ (kluci), $H$ (holky), $Z$ (zvíøátka) a
330 mno¾ina~$T$ kompatibilních trojic (tìch, kteøí se spolu snesou),
331 tedy $T \subseteq K\times H\times Z$.
333 \outp Perfektní podmno¾ina trojic -- tj. taková podmno¾ina trojic, která v~ní¾ se ka¾dý
334 prvek mno¾in $K$, $H$ a~$Z$ vyskytuje právì jednou.
336 \figure{3d_parovani.eps}{Ukázka 3D-párování}{3in}
338 \s{Pøevod 3,3-SATu na 3D-párování:}
339 Kdy¾ chceme ukázat, ¾e na
340 nìco se dá pøevést SAT, potøebujeme obvykle dvì vìci:
341 konstrukci, která bude simulovat promìnné, tedy nìco, co nabývá dvou stavù
342 \<true>/\<false>; a nìco, co bude reprezentovat klauzule a umí zaøídit, aby
343 ka¾dá klauzule byla splnìna alespoò jednou promìnnou.
345 Uva¾ujme takovouto konfiguraci:
349 4 zvíøátka, 2 kluci, 2 dívky a 4 trojice, které oznaèíme $A, B, C, D$. Je¹tì
350 pøedpokládáme, ¾e zvíøátka se mohou úèastnit nìjakých jiných trojic, ale tito
351 ètyøi lidé se vyskytují pouze v~tìchto ètyøech trojicích a~nikde jinde.
352 V¹imneme si, ¾e existují právì dvì mo¾nosti, jak tento obrázek spárovat.
353 Abychom spárovali kluka $k_1$, tak si musíme vybrat $A$ nebo $B$. Kdy¾ si
354 vybereme $A$, $k_1$ i $d_2$ u¾ jsou spárovaní tak¾e si nesmíme vybrat $B$ ani
355 $D$. Pak jediná mo¾nost, jak spárovat $d_1$ a~$k_2$ je $C$. Jedna mo¾nost je
356 tedy vybrat si $A$ a $C$ a jeliko¾ je obrázek symetrický, tak kdy¾ vybereme
357 místo $A$ trojici $B$, dostaneme $B$ a~$D$. V¾dy si tedy vybereme dvì protìj¹í
360 Tyto konfigurace budeme pou¾ívat k~reprezentaci promìnných. Pro ka¾dou
361 promìnnou si nakreslíme takový obrázek a~to, ¾e $A$ bude spárované s~$C$, bude
362 odpovídat tomu, ¾e $x=1$, a~spárování $B$ a~$D$ bude odpovídat $x=0$. Pokud
363 jsme pou¾ili $A$ a~$C$, zvíøata se sudými èísly, tj. $z_2$ a~$z_4$, horní
364 a~dolní, jsou nespárovaná a~pokud jsme pou¾ili $B$ a~$D$, zvíøátka $z_1$
365 a~$z_3$ zùstala nespárovaná. Pøes tato nespárovaná zvíøátka mù¾eme pøedávat
366 informaci, jestli promìnná $x$ má hodnotu \<true> nebo \<false> do dal¹ích
369 Zbývá vymyslet, jak reprezentovat klauzule. Klauzule jsou trojice popø. dvojice
370 literálù, napø. $\kappa = (x \lor y \lor \lnot r)$, kde potøebujeme zajistit,
371 aby $x$ bylo nastavené na $1$ nebo $y$ bylo nastavené na~$1$ nebo $r$ na $0$.
373 \fig{klauzule.eps}{4cm}
375 Pro takovouto klauzuli si poøídíme dvojici kluk-dívka, kteøí budou figurovat
376 ve tøech trojicích se tøemi rùznými zvíøátky, co¾ mají být volná zvíøátka
377 z~obrázkù pro pøíslu¹né promìnné (podle toho, má-li se promìnná vyskytnout
378 s negací nebo ne). A~zaøídíme to tak, aby ka¾dé zvíøátko bylo
379 pou¾ité maximálnì v~jedné takové trojici, co¾ jde proto, ¾e ka¾dý literál se
380 vyskytuje maximálnì dvakrát a~pro ka¾dý literál máme dvì volná zvíøátka,
381 z~èeho¾ plyne, ¾e zvíøátek je dost pro v¹echny klauzule. Pro dvojice se postupuje
384 Je¹tì nám ale urèitì zbude $2p-k$ zvíøátek, kde $p$ je poèet promìnných, $k$
385 poèet klauzulí -- ka¾dá promìnná vyrobí 4 zvíøátka, klauzule zba¹tí jedno
386 a samotné ohodnocení 2 zvíøátka -- tak pøidáme je¹tì $2p-k$ párù
387 kluk-dìvèe, kteøí milují
388 v¹echna zvíøátka, a~ti vytvoøí zbývající trojice.
390 Pokud formule byla splnitelná, pak ze splòujícího ohodnocení mù¾eme vyrobit
391 párování s~na¹í konstrukcí. Obrázek pro ka¾dou promìnnou spárujeme podle
392 ohodnocení, tj. promìnná je $0$ nebo $1$ a~pro ka¾dou klauzuli si vybereme
393 nìkterou z~promìnných, kterými je ta klauzule splnìna. Funguje to ale
394 i~opaènì: Kdy¾ nám nìkdo dá párovaní v~na¹í konstrukci, pak z nìho doká¾eme
395 vyrobit splòující ohodnocení dané formule. Podíváme se, v~jakém stavu je
396 promìnná, a~to je v¹echno. Z~toho, ¾e jsou správnì spárované klauzule, u¾
397 okam¾itì víme, ¾e jsou v¹echny splnìné.
399 Zbývá ovìøit, ¾e na¹e redukce funguje v~polynomiálním èase. Pro ka¾dou klauzuli
400 spotøebujeme konstantnì mnoho èasu, $2p-k$ je také polynomiálnì mnoho a~kdy¾ v¹e
401 seèteme, máme polynomiální èas vzhledem k~velikosti vstupní formule. Tím je
404 \figure{prevody.eps}{Pøevody mezi problémy}{3in}
406 \h{NP-úplné problémy}
408 Dosud jsme zkoumali problémy, které se nás ptaly na to, jestli nìco existuje.
409 Napøíklad jsme dostali formuli a problém splnitelnosti se nás ptal, zda
410 existuje ohodnocení promìnných takové, ¾e formule platí. Nebo v~pøípadì
411 nezávislých mno¾in jsme dostali graf a èíslo $k$ a ptali jsme se, jestli
412 v~grafu existuje nezávislá mno¾ina, která obsahuje alespoò~$k$ vrcholù.
413 Tyto otázky mìly spoleèné to, ¾e kdy¾ nám nìkdo napovìdìl nìjaký objekt, umìli
414 jsme efektivnì øíci, zda je to ten, který hledáme. Napøíklad pokud dostaneme
415 ohodnocení promìnných logické formule, staèí jen dosadit a spoèítat, kde
416 formule dá \<true> nebo \<false>. Zjistit, ¾e nìjaký objekt je ten, který
417 hledáme, umíme efektivnì. Tì¾ké na tom je takový objekt najít. Co¾ vede
418 k~definici obecných vyhledávacích problémù, kterým se øíká tøída problémù NP.
419 Nadefinujeme si ji poøádnì, ale nejdøíve zaèneme tro¹ièku jednodu¹¹í tøídou.
421 \s{Definice:} P je {\I tøída rozhodovacích problémù}, které jsou øe¹itelné
422 v~polynomiálním èase. Jinak øeèeno, problém
423 $L \in {\rm P} \Leftrightarrow \exists $ polynom $f$ a~$\exists$ algoritmus~$A$
424 takový, ¾e $\forall x: L(x)=A(x)$ a $A(x)$ dobìhne v~èase $\O(f(x))$.
426 Tøída P tedy odpovídá tomu, o èem jsme se shodli, ¾e umíme efektivnì øe¹it.
427 Nadefinujme nyní tøídu NP:
429 \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
430 $K\in{\rm P}$ a $\exists$ polynom $g$ takový, ¾e pro
431 $\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$.
433 \s{Pozorování:} Splnitelnost logických formulí je v~NP. Staèí si toti¾ nechat napovìdìt, jak
434 ohodnotit jednotlivé promìnné a pak ovìøit, jestli je formule splnìna. Nápovìda je polynomiálnì
435 velká (dokonce lineárnì), splnìní zkontrolujeme také v~lineárním èase. Odpovíme tedy ano právì
436 tehdy, existuje-li nápovìda, která nás pøesvìdèí, èili pokud je formule splnitelná.
438 \s{Pozorování:} Tøída P le¾í uvnitø NP.
439 V~podstatì øíkáme, ¾e kdy¾ máme problém, který umíme øe¹it v~polynomiálním èase
440 bez nápovìdy, tak to zvládneme v~polynomiálním èase i s~nápovìdou.
442 Problémy z minulé pøedná¹ky jsou v¹echny v NP (napø. pro nezávislou
443 mno¾inu je onou nápovìdou pøímo mno¾ina vrcholù deklarující nezávislost),
444 o jejich pøíslu¹nosti do P ale nevíme nic.
445 Brzy uká¾eme, ¾e to jsou v jistém smyslu nejtì¾¹í problémy v~NP.
448 \s{Definice:} Problém $L$ je NP-{\I tì¾ký} právì tehdy, kdy¾ je na~nìj pøevoditelný
449 ka¾dý problém z~NP (viz definici pøevodù z minulé pøedná¹ky).
451 Rozmyslete si, ¾e pokud umíme øe¹it nìjaký NP-tì¾ký problém v~polynomiálním èase,
452 pak umíme vyøe¹it v~polynomiálním èase v¹e v~NP, a tedy ${\rm P}={\rm NP}$.
454 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é.
456 \s{Definice:} Problém $L$ je NP-{\I úplný} právì tehdy, kdy¾ $L$ je NP-tì¾ký a $L \in {\rm NP}$.
458 NP-úplné problémy jsou tedy ve~své podstatì nejtì¾¹í problémy, které le¾í v~NP.
459 Kdybychom umìli vyøe¹it nìjaký NP-úplný problém v~polynomiálním èase, pak
460 v¹echno v~NP je øe¹itelné v~polynomiálním èase. Bohu¾el to, jestli nìjaký
461 NP-úplný problém lze øe¹it v~polynomiálním èase, se neví. Otázka, jestli
462 ${\rm P}={\rm NP}$, je asi nejznámìj¹í otevøený problém v~celé teoretické
465 Kde ale nìjaký NP-úplný problém vzít? K~tomu se nám bude velice hodit následující vìta:
467 \s{Vìta (Cookova):} SAT je NP-úplný.
469 \>Dùkaz je znaènì technický, pøibli¾nì ho naznaèíme pozdìji. Pøímým dùsledkem
470 Cookovy vìty je, ¾e cokoli v~NP je pøevoditelné na SAT.
471 K dokazování NP-úplnosti dal¹ích problémù pou¾ijeme následující vìtièku:
473 \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ý.
476 Tuto vìtièku staèí dokázat pro NP-tì¾kost, NP-úplnost plyne okam¾itì z~toho, ¾e
477 problémy jsou NP-tì¾ké a le¾í v~NP (podle pøedpokladu).
479 Víme, ¾e $L$ se dá pøevést na~$M$ nìjakou funkcí~$f$. Jeliko¾ $L$ je NP-úplný,
480 pak pro ka¾dý problém $Q\in{\rm NP}$ existuje nìjaká funkce~$g$, která pøevede
481 $Q$ na~$L$. Staèí tedy slo¾it funkci~$f$ s~funkcí~$g$, èím¾ získáme funkci pracující
482 opìt v~polynomiálním èase, která pøevede~$Q$ na~$M$. Ka¾dý problém z~NP se tedy
483 dá pøevést na problém~$M$.
486 \s{Dùsledek:} Cokoliv, na co jsme umìli pøevést SAT, je také NP-úplné.
487 Napøíklad nezávislá mno¾ina, rùzné varianty SATu, klika v~grafu~\dots
489 Jak taková tøída NP vypadá? Pøedstavme si v¹echny problémy tøídy NP, jakoby seøazené
490 shora dolu podle obtí¾nosti problémù (tedy navzdor gravitaci), kde porovnání dvou
491 problémù urèuje pøevoditelnost (viz obrázek).
493 \figure{p-np.eps}{Struktura tøídy NP}{2.5cm}
495 Obecnì mohou nastat dvì situace, proto¾e nevíme, jestli ${\rm P}={\rm NP}$.
496 Jestli ano, pak v¹echno je jedna a ta samá tøída. To by bylo v nìkterých
497 pøípadech nepraktické, napø. ka¾dá ¹ifra by byla jednodu¹e rozlu¹titelná.
498 \foot{Poznámka o ¹ifrách -- libovolnou funkci vyèíslitelnou v polynomiálním
499 èase bychom umìli v polynomiálním èase také invertovat.}
500 Jestli ne, NP-úplné problémy urèitì nele¾í v P, tak¾e P a NP-úplné problémy
501 jsou dvì disjunktní èásti NP. Také se dá dokázat (to dìlat nebudeme, ale je
502 dobré to vìdìt), ¾e je¹tì nìco le¾í mezi nimi, tedy ¾e existuje problém, který
503 je v~NP, není v~P a není NP-úplný (dokonce je takových problémù nekoneènì mnoho,
504 v nekoneènì tøídách).
506 \s{Katalog NP-úplných problémù}
508 Uká¾eme si nìkolik základních NP-úplných problémù. O~nìkterých jsme to dokázali
509 na~minulé pøedná¹ce, o~dal¹ích si to doká¾eme nyní, zbylým se na~zoubek podíváme
515 \:SAT (splnitelnost logických formulí v~CNF)
516 \:3-SAT (ka¾dá klauzule obsahuje max.~3 literály)
517 \:3,3-SAT (a navíc ka¾dá promìnná se vyskytuje nejvý¹e tøikrát)
518 \:SAT pro obecné formule (nejen CNF)
519 \:Obvodový SAT (není to formule, ale obvod)
523 \:Nezávislá mno¾ina (existuje mno¾ina alespoò~$k$ vrcholù taková, ¾e ¾ádné dva nejsou propojeny hranou?)
524 \:Klika (existuje úplný podgraf na~$k$ vrcholech?)
525 \: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?)
526 \:Barvení grafu (lze obarvit vrcholy $k$~barvami tak, aby vrcholy stejné barvy nebyly nikdy spojeny hranou? NP-úplné u¾ pro~$k=3$)
527 \:Hamiltonovská cesta (cesta obsahující v¹echny vrcholy [právì jednou])
528 \:Hamiltonovská kru¾nice (kru¾nice, která nav¹tíví v¹echny vrcholy [právì jednou])
532 \:Batoh (nejjednodu¹¹í verze: dána mno¾ina èísel, zjistit, zda existuje podmno¾ina se zadaným souètem)
533 \:Batoh -- optimalizace (podobnì jako u pøedchozího problému, ale místo mno¾iny èísel máme mno¾inu
534 pøedmìtù s vahami a cenami, chceme co nejdra¾¹í podmno¾inu její¾ váha nepøesáhne zadanou kapacitu
536 \:Loupe¾níci (lze rozdìlit danou mno¾inu èísel na~dvì podmno¾iny se stejným souètem)
537 \:$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\}$)
538 \:Celoèíselné lineární programování (existuje vektor nezáporných celoèísených $x$ takový, ¾e $Ax \leq b$ ?)
542 \h{Náznak dùkazu Cookovy vìty}
544 Abychom mohli budovat teorii NP-úplnosti, potøebujeme alespoò jeden problém,
545 o kterém doká¾eme, ¾e je NP-úplný, z definice. Cookova vìta øíká o NP-úplnosti
546 SAT-u, ale nám se to hodí dokázat o tro¹ku jiném problému -- {\I obvodovém SAT-u}.
548 \>{\I Obvodový SAT} je splnitelnost, která nepracuje s~formulemi, ale s~booleovskými
549 obvody (hradlovými sítìmi). Ka¾dá formule se dá pøepsat do booleovského obvodu,
550 který ji poèítá, tak¾e dává smysl zavést splnitelnost i pro obvody. Na¹e obvody
551 budou mít nìjaké vstupy a~jenom jeden výstup. Budeme se ptát, jestli se vstupy
552 tohoto obvodu dají nastavit tak, abychom na výstupu dostali \<true>.
554 \>Nejprve doká¾eme NP-úplnost {\I obvodového SAT-u} a~pak uká¾eme, ¾e se dá
555 pøevést na obyèejný SAT v~CNF. Tím bude dùkaz Cookovy vìty hotový. Zaènìme
558 \s{Lemma:} Nech» $L$ je problém v P. Potom existuje polynom $p$ a algoritmus,
559 který pro $\forall n \ge 0$ spoète v èase $p(n)$ hradlovou sí» $Bn$ s $n$ vstupy
560 a 1 výstupem takovou, ¾e $\forall x \in \{ 0, 1 \}^n : Bn(x) = L(x)$.
563 Náznakem. Na základì zku¹eností z Principù poèítaèù intuitivnì chápeme poèítaèe
564 jako nìjaké slo¾ité booleovské obvody, jejich¾ stav se mìní v~èase. Uva¾me tedy
565 nìjaký problém $L \in {\rm P}$ a polynomiální algoritmus, který ho øe¹í. Pro vstup
566 velikosti~$n$ dobìhne v~èase~$T$ polynomiálním v~$n$ a spotøebuje $\O(T)$ bunìk pamìti.
567 Staèí nám tedy \uv{poèítaè s~pamìtí velkou $\O(T)$}, co¾ je nìjaký booleovský obvod
568 velikosti polynomiální v~$T$, a~tedy i v~$n$. Vývoj v~èase o¹etøíme tak, ¾e sestrojíme~$T$
569 kopií tohoto obvodu, ka¾dá z~nich bude odpovídat jednomu kroku výpoètu a bude
570 propojena s~\uv{minulou} a \uv{budoucí} kopií. Tím sestrojíme booleovský obvod,
571 který bude øe¹it problém~$L$ pro vstupy velikosti~$n$ a bude polynomiálnì velký
575 Pro dùkaz následující vìty si dovolíme drobnou úpravu v~definici tøídy NP.
576 Budeme chtít, aby nápovìda
577 mìla pevnou velikost, závislou pouze na~velikosti vstupu (tedy: $\vert y \vert
578 = g(\vert x \vert)$ namísto $\vert y \vert \le g(\vert x \vert)$). Proè je taková
579 úprava BÚNO? Jistì si dovedete pøedstavit,
580 ¾e pùvodní nápovìdu doplníme na po¾adovanou délku nìjakými \uv{mezerami}, které
581 program ignoruje. (Tedy upravíme program tak, aby mu nevadilo, ¾e dostane na
582 konci nápovìdy nìjak kódované mezery.)
584 \s{Vìta:} Obvodový SAT je NP-úplný.
587 Máme tedy nìjaký problém $L$ z~NP a~chceme dokázat, ¾e $L$ se dá pøevést
588 na~obvodový SAT (tj. NP-tì¾kost). Kdy¾ nám nìkdo pøedlo¾í nìjaký vstup $x$
589 (chápeme jako posloupnost $x_1, x_2, \ldots, x_n$),
590 spoèítáme velikost nápovìdy $g(n)$. Víme, ¾e kontrolní
591 algoritmus~$K$ (který kontroluje, zda nápovìda je správnì) je v~P. Vyu¾ijeme
592 pøedchozí lemma, abychom získali obvod, který pro konkrétní velikost vstupu
593 $x$ poèítá to, co kontrolní algoritmus $K$. Na vstupu tohoto obvodu bude $x$
594 (vstup problému $L$) a~nápovìda~$y$. Na výstupu nám øekne, jestli je nápovìda
595 správná. Velikost vstupu tohoto obvodu bude tedy $p(g(n))$, co¾ je také polynom.
597 \fig{kobvod.eps}{2.3cm}
599 \>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ý.
601 \>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á
602 v~polynomiálním èase pøevést na obvodový SAT.
604 \>Obvodový SAT je v NP triviálnì -- staèí si nechat poradit vstup, sí»
605 topologicky setøídit a v~tomto poøadí poèítat hodnoty hradel.
608 \s{Lemma:} Obvodový SAT se dá pøevést na 3-SAT.
611 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ì.
613 \>{\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é:
614 $$\matrix{ (x \lor y), \cr
615 (\neg{x} \lor \neg{y}). \cr }
617 \vcenter{\hbox{\epsfxsize=0.7cm\epsfbox{not.eps}}}
620 \>{\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:
623 x\ \&\ y \Rightarrow z \cr
624 \neg{x} \Rightarrow \neg{z} \cr
625 \neg{y} \Rightarrow \neg{z} \cr
631 (z \lor \neg{x} \lor \neg{y}) \cr
636 \vcenter{\hbox{\epsfxsize=0.7cm\epsfbox{and.eps}}}
639 \>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.
643 Kdy¾ jsme zavádìli SAT, omezili jsme se jen na formule, které jsou
644 v~konjunktivní normální formì (CNF). Teï u¾ víme, ¾e splnitelnost obecné
645 booleovské formule doká¾eme pøevést na obvodovou splnitelnost a tu pak
646 pøevést na 3-SAT. Opaèný pøevod je samozøejmì triviální, tak¾e obecný SAT
647 je ve~skuteènosti ekvivalentní s~na¹ím \uv{standardním} SATem pro CNF.
projects / ads2.git / blob