19 Složitost Základní otázka teorie složitosti je „jak rychle dokážeme nějaký problém řešit". Budeme přitom vycházet z modelu Turingova stroje jako základního výpočetního modelu. Abychom mohli na tuto otázku smysluplně odpovídat, musíme se omezit pouze na ty Turingovy stroje, které na všech vstupech ukončí svůj výpočet. Studium teorie složitosti se tedy omezuje na třídu rekurzivních jazyků, proto se jí také říká subrekurzivní vyčíslitelnost. 19.1 Model složitosti Složitost je v nejobecnějším významu míra využití zdroje. Mezi základní zdroje, které může algoritmus využívat, je především čas a paměť (prostor). Můžeme se ovšem ocitnout v situaci, kdy máme pro výpočty jiné omezení, např. počet přístupů na disk, počet přístupů do sítě, energie nebo též množství nějakého vzácného prvku. Požadavek na nízkou časovou náročnost se ovšem zdá být ve většině případů univerzální, proto jeho studium matematické teorii složitosti a algoritmů dominuje. Definice. Složitost Turingova stroje M definujeme postupně jako následující zobrazení: • časová složitost stroje M na vstupu jako zobrazení t m : S* —>• N, kde t m (w) je počet kroků, které provede stroj M na vstupu w. V případě nedeterministického stroje bereme maximum ze všech možných výpočtů na daném vstupu. • časová složitost stroje M jako zobrazení Tm : No —>• N, kde Tx(íí) je nej větší počet kroků, které stroj M provede na vstupu délky n, tj: TmÍ™) = max{Tx(w) | \w\ = n} • prostorová složitost stroje M na vstupu jako zobrazení sm : S* —>• N, kde sm(w) je počet políček na pásce, které stroj M navštíví během výpočtu na slově w. V případě nedeterministického stroje bereme opět maximum ze všech možných výpočtů na daném vstupu. • prostorová složitost stroje M jako zobrazení S m ■ N0 —>• N, kde SVi(n) je maximální počet políček, které navštíví stroj M během svého výpočtu na vstupu délky n, tj: SmÍ71) = max{s_A/f(w) | \w\ = n} Říkáme také, že stroj M pracuje v čase T^(?i) a v prostoru SmÍ71)- Poznámka. V definici složitosti bereme maximum přes všechny možné vstupy dané velikosti. Odpovídá to konvenci počítat vždy s nejhorším možným případem. Existují ale i jiné přístupy. Bylo by např. možné počítat průměrnou složitost, operace maxima by se nahradila aritmetickým průměrem. Tohoto přístupu se využívá především v teorii náhodnostních algoritmů, kde se složitost definuje jako střední hodnota (vážený aritmetický průměr). Poznámka. Uvedená definice složitosti silně závisí na volbě Turingova stroje jako základního výpočetního modelu. Volbou jiného modelu se tato definice může značně lišit. Tento problém budeme rozebírat dále v textu. 1 19.2 Porovnávání růstu Motivace. Protože časová i prostorová složitost stroje jsou definovány jako funkce N^Na ještě obecněji jako funkce N —>• R+ (abychom se nemuseli zabývat zaokrouhlováním), je studium teorie složitosti především studiem funkcí tohoto typu. Zastavme se na krátce u dvou problémů: a) Máme-li dva stroje, které řeší tentýž problém, který z nich jej řeší lépe? Intuitivní odpovědí je pochopitelně ten, který jej řeší rychleji. Co ale znamená toto „rychleji"? Složitost jsme si nezaváděli jako čísla, která umíme snadno srovnat, ale funkce a ty nemusí být vždy porovnatelné. Příkladem jsou funkce lOn a n2 pro n < 10 platí lOn > n2 a pro n > 10 zase lOn < n2, tak kterou z nich prohlásit za „tu, s menší hodnotou"? Vzhledem k praktickým omezením dnešních počítačů nás zajímá, jak se složitost vyvíjí pro velké vstupy, tj. pro n —>• oo. Zajímá nás tzv. asymptotické chování funkcí. Řečeno laicky, pro porovnání nám slouží kritérium, zda jedna funkce někdy tu druhou přeroste. b) Je tu ještě další problém, který musíme vzít v potaz před následující definicí. Každý Turingův stroj můžeme „lineárně urychlovat" tím, že jej necháme namísto s jednotlivými symboly počítat s dvojicemi (nebo obecně fc-ticemi) symbolů. Tento fakt se shrnuje do tvrzení, že pro každý stroj M a libovolné to e N existuje ekvivalentní stroj M! splňující: to Toto zrychlení je tedy vždy nejvýše lineární a celková složitost nemůže klesnout pod n. Tyto dvě úvahy musíme zahrnout do naší definice. Tato definice tedy musí zohledňovat chování funkcí pro vysoké hodnoty n a musí ignorovat násobení konstantou. V tomto momentě už by měla následující volba připadat naprosto přirozeně. Definice. Řekneme, že funkce / neroste asymptoticky rychleji než funkce g, jestliže existují n0 e N a c e R+ taková, že pro každé n > n0 platí f(n) < cg(n). O funkci g říkáme, že je asymptotická horní závora pro f. Množinu funkcí, které nerostou asymptoticky rychleji než g značíme 0{g). Příklad 1. Platí lOn e 0(n2) volbou no = 10 a c = 1 nebo volbou no = 1 a c= 10. Příklad 2. Při poměřování asymptotického růstu nezáleží na základech logaritmů, totiž loga n e C(logb n) pro libovolné a,b > 1. To vyplývá ze vzorce: loga n = loga b ■ logb n Dvě logaritmické funkce o různých základech se liší pouze násobkem konstantou. U logaritmů tedy nebudeme uvádět základ, popřípadě si jej při výpočtech volit podle potřeby. Příklad 3. Platí log n e O (n). To vyplyne, jakmile ukážeme, že log n < n pro každé n e N. To se dá ukázat geometricky nebo indukcí, totiž log 1 = 0 < 1 a za předpokladu, že tvrzení platí pro n, je indukční krok tvaru: log(n + 1) < log(n + n) = log n + log 2 = log n + 1 < n + 1 2 Věta 19.1. Vlastnosti symbolu O: a) Pro libovolnou funkci /: N R+ platí f eO(f). b) Pro libovolné funkce f,g,h: N —>• M+ platí: /eO(ff)AffeO(ft)=>/eO(/i) Relaci „neroste asymptoticky rychleji než" je reflexivní a tranzitivní (není uspořádáním, neboť není antisymetrická), proto ji můžeme intuitivně chápat jako „menší nebo rovno". K tomu dostáváme přidružené pojmy: pojem analogie značka neroste rychleji < O neroste pomaleji > Q roste stejně rychle = 6 roste pomaleji < o roste rychleji > uj Definice. Uveďme formální definice všech předchozích pojmů: 0{g) = {/: N0 R | 3n0 e N, c e M+Vn > n0 : f (n) < cg(n)} tt(g) = {/= N0 -)■ M | 3n0 G N, c G M+Vn > n0 : /(n) > cg(n)} Q(ff) = {/: No -> M | 3n0 e N, ci, ca e M+Vn > n0 : clí?(n) < f (n) < c2g(n)} Dále: o(ff) = (/:N0-^M| lim 44 = °1 w(<7) = (/:N„->K| lim 44=^1 Cvičení 1. Uspořádejte následující funkce podle růstu: 2™ n log n n! log log n e™ n5 — 100n + 3 n™ log n! log5 n 1 22" arctan n n y/2™ (2n)\ (n!)2 log n2 Cvičení 2. Dokažte následující implikace: a) / G o( f f e o(ff) Asymptotickou symboliku můžeme používat spolu s některými základními aritmetickými operacemi: a) Výrazem O(f) + O (g) většinou dáváme najevo, že stroj provádí za sebou dva úseky v časech O(f) a O (g). Je potom logické klást: O(f) + O(g) = 0(f + g) 3 b) Podobně můžeme použít O(f) ■ 0{g) = O(fg) pro případy, kdy stroj opakuje úsek, jehož časová složitost je O(g), a počet iterací je asymptoticky ohraničen funkcí /. Díky tomu stačí znát odhad počtu iterací a ne jeho přesný počet. c) V některých případech bude užitečné psát 2°(n\ je ale třeba si uvědomit 20(n) ^ 0(2n), protože např: 0(2") ^ 4™ = 22n e 2°{n) 19.3 Vliv modelu Jak už bylo řečeno, volba výpočetního modelu silně ovlivňuje rychlost výpočtů. Např. RAM (random access machine) pracující v čase 0(f(n)) lze převést na vícepáskový deterministický Turingův stroj pracující v čase C(/3(n)(/(n)+n)2). Některé vztahy probereme formálně. Věta 19.2 (Cena za jednu pásku.). Pro každý vícepáskový Turingův stroj pracující v čase 0(f(n)) existuje ekvivalentní jednopáskový Turingův stroj pracující v čase C(/2(n)). Důkaz. Obsahy všech pásek zapíšeme za sebe a každý krok výpočtu vícepás-kového stroje simulujeme průchodem celé pásky. Těchto průchodů je potřeba 0(f(n)). Bylo-li k pásek, pak máme za sebou k úseků délky nejvýše 0(f(n)). Celkem se provede nejvýše 0(kf2(n)) = C(/2(n)) kroků. □ Věta 19.3 (Cena za determinizmus.). Pro každý nedeterministický Turingův stroj pracující v čase 0(f(n)) existuje ekvivalentní deterministický Turingův stroj pracující v čase Důkaz. Připomeňme, že převod nedeterministického stroje na deterministický provádíme tak, že procházíme výpočetní strom nedeterministického stroje do šířky. Označme míru větvení tohoto stroje a. Potom aP(f(n^ je horní závora pro počet uzlů v tomto stromě. Na druhé pásce si přitom zaznamenáváme polohu ve stromě pomocí řetězce délky 0(f(n)). Složitost této simulace je 0(f(n)a0(f(n^) = 2°(f(n>>\ Převod na jednopáskový stroj má kvadratickou cenu, což je stále (2°^{-n^f = 2°^^. □ Cvičení 3. Mějme jazyk L = {anbn \ n > 1}. Nalezněte: a) Deterministický jednopáskový stroj rozpoznávající L v čase 0(n2). b) Deterministický dvoupáskový stroj rozpoznávající L v čase 0{n). c) Deterministický jednopáskový stroj rozpoznávající L v čase O(nlogn). Stačí uvádět myšlenky, není potřeba stroje formálně konstruovat. 19.4 Třídy složitosti Protože můžeme mít více Turingových strojů, které řeší daný problém, definujeme složitost problému přirozeně jako složitost toho nej rychlejšího z nich. 4 Definice. Pro libovolnou funkci / : No —>• R definujeme následující třídy problémů: TIME (/) = {L | existuje deterministický Turingův stroj M akceptující L a Tm e O(f)} NTIME (/) = {L | existuje nedeterministický Turingův stroj N akceptující L a TV G O(f)} SPACE (/) = {L | existuje deterministický Turingův stroj M akceptující L a S m "= NSPACE (/) = {L | existuje nedeterministický Turingův stroj N akceptující L a SV G O(f)} Poznámka. Deterministický stroj je speciálním případem nedeterministického, proto platí: TIME (/) C NTIME (/) SPACE (/) C NSPACE (/) Poznámka. Žádný stroj nemůže navštívit více políček pásky, než kolik má k dispozici kroků. Proto je prostorová složitost vždy menší nebo stejná jako časová. Z toho dostáváme další dva vztahy: TIME (/) C SPACE (/) NTIME (/) C NSPACE (/) Definice. Definujeme časové třídy problémů: P = |J TIME (nfe) EXPTIME = |J TIME (t" feeN feeN NP = |J NTIME (nfe) NEXPTIME = \j NTIME [t" feeN feeN Poznámka. Převod vícepáskového na jednopáskový stroj měl kvadratickou cenu. Polynomiální cenu mají i převody mezi jinými modely (RAM, stroje s více počítadly atd.) Výjimkou je vztah mezi deterministickými a nedeterministickými modely, kde se zatím nepodařil ukázat lepší než exponenciální nárůst. Proto se pro nedeterministické výpočty vyhradily samostatné třídy složitosti a v následující větě již neberou v úvahu. Třídy P, NP, EXPTIME a NEXPTIME nejsou citlivé na volbu výpočetního modelu, říkáme, že jsou robustní. Poznámka. Protože nárůst složitosti při převodu nedeterministického stroje na deterministický je nejvýše asymptoticky exponenciální, dostáváme následující inkluze: P C NP C EXPTIME C NEXPTIME Na tomto místě uveďme, že doposud nebylo dokázáno, zda inkluze P C NP je či není ostrá, tj. zda ve skutečnosti nenastává rovnost P = NP. Tento „P rovná se NP" problém se ukázal obzvláště náročný a v roce 2000 na jeho vyřešení Clay Mathematics Institute vypsal odměnu jeden milion dolarů. Přitom řešení tohoto problému těsně souvisí s efektivitou většiny moderních kryptografických protokolů a jejich bezpečností. Pokud by se totiž ukázalo, že P = NP, jedním z důsledků by byla existence efektivního algoritmu na prolomení šifer s veřejným klíčem. Cvičení 4. Ukažte, že třída P je uzavřena na operace doplňku, sjednocení, průniku i komplementu. 5 19.5 Polynomiální vyčíslitelnost Z praktického hlediska jsou použitelné pouze algoritmy pracující v polynomiálním čase, tzn. problémy v třídě P, i když existují i výjimky. Např. používaným algoritmem pro řešení systému lineárních nerovnic je simplexový algoritmus, ačkoli má asymptoticky exponenciální složitost a ačkoli existují algoritmy pro tento problém pracující v polynomiálním čase. Příklad 4. Uvažme problém cesty definovaný jako problém příslušnosti do jazyka: PATH = {G#s#í I graf G obsahuje cestu z s do ŕ} Platí PATH e P. Příklad 5. Uvažme problém hamiltonovské cesty jako problém příslušnosti do jazyka: HAMPATH = {G#s#í | v grafu G existuje hamiltonovská cesta z s do ŕ} Platí HAMPATH e NP. Nedeterministický stroj pro tento jazyk bude pracovat následovně: Nedeterministický stroj konstruuje cestu z s tak, že vždy nedeterministicky zvolí následující hranu do dalšího vrcholu. Je-li poslední vrchol t a navštívili jsme všechny vrcholy grafu právě jednou, pak akceptujeme, jinak zamítáme. Tento algoritmus má zřejmě polynomiální složitost a akceptuje právě tehdy, když v grafu existuje hamiltonovská cesta z s do t. Příklad 6. Problém rozpoznání prvočíselnosti: COMPOSITES = {n e N | n = pq pro nějaká p, q > 1} Potom COMPOSITES e NP. Nedeterministický stroj uhodne dvě čísla p a q, vynásobí je a výsledek porovná se vstupem, pokud se hodnoty shodují, pak akceptuje, jinak zamítá. Všechny předchozí příklady problémů z NP měli společnou strukturu: Vždy jsme nedeterministicky uhodli řešení a poté deterministicky ověřili, že uhádnuté řešení splňovalo zadání. Ukazuje se, že toto schéma přesně vystihuje třídu NP. Jsou to právě ty problémy, které lze polynomiálně verifikovat. Provedeme formalizaci: Definice. Polynomiální verifikátor pro jazyk L je deterministický Turingův stroj V takový, že w e L právě tehdy, když existuje řetězec c takový, že V akceptuje w#c v polynomiálním čase vzhledem ke \w\. Věta 19.4. Platí L e NP právě tehdy, když existuje polynomiální verifikátor pro L. Důkaz. =^>: Je-li L e NP, pak podle definice existuje nedeterministický Turingův stroj N akceptující L v polynomiálním čase. Mějme w e L libovolné. Za řetězec c zvolme posloupnost cifer, která kóduje seznam nedeterministických výběrů, které provedl stroj na vstupu w. Polynomiální verifikátor V bude pracovat přesně jako stroj Aí, přičemž nedeterministické volby bude provádět deterministicky podle řetězce c. Zřejmě je V polynomiální, protože byl polynomiální a akceptuje právě w#c pro w G L. 6 <=: Máme-li polynomiální verifikátor V pro jazyk L, pak můžeme sestrojit nedeterministický stroj N akceptující L jako stroj, který dostane na vstupu w, nedeterministicky uhádne řetězec c a poté simuluje činnost stroje V na w#c. Z definice polynomiálního verifikátoru vyplývá, že stroj N pracuje s polynomiální složitostí. Proto L e NP. □ Cvičení 5. Dokažte, že třída NP je uzavřena na sjednocení, průnik i zřetězení. Poznámka. Otázka uzavřenosti třídy NP na komplement je dodnes otevřeným problémem. Cvičení 6. Definujeme třídu: coNP = {L° | L e NP} Rozhodněte, zda platí následující tvrzení: a) NPC = coNP b) Třída coNP je uzavřena na průnik. c) Li e NP, L2 C Li, L2 G coNP => Li\L2 A e NP d) A (f. NP B (f. NP Analogicky teorii vyčíslitelnosti definujeme koncept těžkého a úplného problému, tentokrát vzhledem k polynomiální redukci. Definice. Nechť C je třída jazyků a A libovolný jazyk. Řekneme, že A je a) C-těžký, jestliže C

x V -ny) A (->x V y) A (x V ^z) d) (mV^dV -w) A (w V ^y V z) A (w V ^z V x) A (x V y V z) Věta 19.6 (Cook, Levin). Problém SAT je NP-těžký. Důkaz. Důkaz nebudeme uvádět, neboť je převážně technicky. Myšlenka je ta, že každý Turingův stroj přeložíme do výrokové formule, přičemž tato formule je splnitelná právě tehdy, když stroj akceptuje vstup. Navíc tato formule má délku úměrnou délce výpočtů původního stroje. Pokud tedy stroj pracoval v polynomiálním čase, je tato redukce polynomiální. □ Příklad 7. Problém 3SAT je podproblém SAT určit, zda zadaná formule v 3-CNF je splnitelná. Formule je v 3-CNF, jestliže je v konjunktivní normální formě a každá klauzule má maximálně tři literály. Ukážeme, že 3SAT je NP-úplný pomocí redukce SAT < 3SAT. Pro každou formuli p v CNF sestrojíme formuli tp v 3-CNF takovou, že p je splnitelná právě tehdy, když je tp splnitelná (formule p a tp nemusí být ekvivalentní). Zřejmě můžeme zachovat všechny klauzule, které neobsahují více než tři literály. Každou zbývající klauzuli x\ V ... V xn (n > 3) ve if nahradíme formulí v 3-CNF: (xi V x2 V yi) A ... A (^yt V xí+3 V yl+1) A ... A {^yn-i V x„_i V x„) kde yi,..., yn-4 jsou nové proměnné, které se nevyskytují v původní formuli ip. Tato redukce je přitom polynomiální, pro každou klauzuli přidáme asymptoticky lineární počet nových proměnných a vše můžeme provést v jedním průchodem formule ip. Příklad 8. Mnoho grafových problémů je NP-úplných, proveďme důkaz pro následující problém kliky: CLIQUE = {G#k | graf G obsahuje kliku velikosti k} Připomeňme, že klika je úplný podgraf. Provedeme redukci problému 3SAT. Mějme formuli ip v 3-CNF s k klauzulemi. Vytvoříme graf, jehož vrcholy jsou všechny literály ze všech klauzulí. Dva literály jsou spojeny hranou právě tehdy, když se nacházejí v jiné klauzuli a jsou navzájem kompatibilní (jeden není negací druhého). Potom původní formule byla splnitelná právě tehdy, když takto sestrojený graf obsahuje kliku velikosti k. Tato redukce je přitom polynomiální. Cvičení 8. Dokažte, že problém podgrafového izomorfizmu je NP-úplný. Tento problém je definován jako problém pro dané dva grafy H a, G určit, zda G obsahuje H jako svůj podgraf (je izomorfní nějakému jeho podgrafu). 8 19.7 Prostorové třídy složitosti Prostor je kvalitativně odlišný zdroj než čas, především jej můžeme používat opakovaně (tzv. „recyklovat"), což vede k tomu, že celková prostorová složitost problémů bude nižší než jejích časová složitost. Změna modelu také nevede k tak velkým cenám, jako tomu bylo u času. Např. převod vícepáskového stroje na jednopáskový nemá žádný vliv na použitý počet políček, celková složitost bude prostě součet všech použitých políček na všech páskách. Věta 19.7. Pro každou funkci /: N0 R+ platí: SPACE (/(n)) C TIME (2°^A NSPACE (/(n)) C NTIME (2°^™» Důkaz. Zvolme za k velikost páskové abecedy stroje, který pracuje v prostoru 0(f(n)). Potom tento stroj může navštívit pouze fc°'^n" možných konfigurací, přičemž v každém kroku výpočtu navštíví právě jednu. Stroj tedy musí skončit v čase 2°tf(")). □ Definice. Zadefinujeme analogické prostorové třídy: PSPACE = |J SPACE (nfe) EXPSPACE = (J SPACE (V* feeN feeN NPSPACE = |J NSPACE (nfe) NEXPSPACE = \j NSPACE (2' feeN feeN Příklad 9. Pomocí polynomiální redukce můžeme dokázat inkluzi: NP C PSPACE Vzpomeňme si, že problém SAT je NP-úplný. Tento problém přitom snadno vyřešit v lineární prostoru. Stačí, když si na druhou pásku vypíšeme nějakou valuaci (což je vlastně posloupnost nul a jedniček) proměnných a zkusíme formuli vyhodnotit (třeba na další pásce). Přitom nespotřebujeme více prostoru, než je trojnásobek vstupu (obsah druhé ani třetí pásky nikdy nepřekročí délku formule). Protože polynomiální redukce musí probíhat také v polynomiálním prostoru (nemůžeme spotřebovat více políček, než máme k dispozici kroků), je každý problém z NP v PSPACE. Věta 19.8 (Savitch). Pro libovolnou funkci / : N0 —>• N splňující f(n) > n platí: NSPACE (/(n)) C SPACE (/2(n)) Důkaz. Mějme nedeterministický stroj N s prostorovou složitostí f(n). Stroj N upravíme tak, aby měl pouze jednu akceptující konfiguraci - třeba tak, že stroj donutíme před akceptováním smazat obsah pásky a posunout hlavu úplně vlevo. Označme tuto akceptující konfiguraci cacc. Ekvivalentní deterministický stroj M implementuje proceduru comp(ci,c2,t), která akceptuje, pokud lze ve stroji N během nejvýše t kroků přejít z konfigurace c\ do konfigurace c2, jinak zamítá. Označíme-li cw iniciální konfiguraci pro vstup w, potom stačí, abychom na začátku výpočtu spustili comp(cw,cacc,k^n^), kde k je velikost páskové abecedy. Stroj s prostorovou složitostí f(n) totiž nemůže navštívit více než k-f^ konfigurací. Proceduru comp pro trojici [c\,c2,ť) implementujeme rekurzivně: 9 a) Jestliže t = 1, ověříme pouze, jestli c\ = c2 nebo c\ hjv- c2. b) Jestliže t > 1, zavoláme comp(ci,c, |_r/2J) a comp(c,c2, \t/2~\) pro každou konfiguraci c délky /(n). Akceptujeme, jestliže obě volání akceptují Prostorová složitost každého volání procedury comp je |ci| + |c2| + |c| + |í|+C G 0(f(n)) (C je nějaká konstanta). Celková prostorová složitost stroje M je tedy prostorová složitost procedury comp krát hloubka rekurze, tedy: TM{n) G log = G(/2(n)) □ Poznámka. Důsledkem Savitchovy věty jsou rovnosti: NPSPACE = PSPACE NEXPSPACE = EXPSPACE Dohromady jsme již dokázali následující řetězec: PCNPC PSPACE = NPSPACE C EXPTIME C NEXPTIME Cvičení 9. Určete vztahy inkluze/rovnost mezi následujícími dvojicemi složi-tostních tříd. Své tvrzení zdůvodněte. a) TIME (n2) a TIME (n3) b) SPACE (2n2) a SPACE (lOOn2) c) SPACE (n2) a TIME (n2) d) NSPACE (n2) a SPACE (n5) e) P a TIME (2™) Příklad 10. Jen pro zajímavost uveďme příklad problému, který je PSPACE-úplný. Jde opět o případ problému splnitelnosti, tj. určit pro danou formuli, zda existuje valuace, která ji splňuje. Formule tentokrát bereme z množiny kvantifikovaných výrokových formulí, jsou to výrokové formule se všeobecnými a existenčními kvantifikátory (kvantifikuje se přes množinu {0,1}). 10