Vztah teorie vyčíslitelnosti a teorie složitosti IB102 Automaty, gramatiky a složitost, 28.11.2016 1/28 Časová složitost algoritmu ■ počet "kroků" výpočtu ■ závisí na vstupu a výpočetním modelu ■ jako základní model použijeme Turingův stroj ■ zkoumáme nejhorší případ, tedy maximální počet kroků v závislosti na délce vstupu ■ lze zkoumat i průměrný případ IB102 Automaty, gramatiky a složitost, 28.11.2016 2/28 Časová složitost deterministického Turingova stroje Definice. Nechť M je úplný deterministický (jednopáskový nebo vícepáskový) Turingúv stroj se vstupní abecedou Z. Pro každé 1/1/ e Z definujeme tM(w) jako počet kroků výpočtu stroje M na vstupu w. Časová složitost stroje M je pak funkce TM : N0 N definovaná vztahem TM(ri) = max{ŕM(i/i/) | w e Tn}. Říkáme, že M pracuje v čase TM(n). IB102 Automaty, gramatiky a složitost, 28.11.2016 3/28 Příklad M = ({Qo, q^, Qacc, qrej], {0,1}, {0,1, >, □}, >, u, S, q0l qacc, qrej) S > 0 1 u qo (Qo,>,R) (cfe,0,fí) (Q1,1, (qacc-, ~■> ") q} (Qrej, ~, -) (Qi, 1, (qacc-, ~■> ") IB102 Automaty, gramatiky a složitost, 28.11.2016 4/28 Příklad M = ({Qo, q^, r, S0, , qacc, qrej}, {O, 1 }, {O, 1, X, >, □}, >, U, 5, Cfo, Qacc, <7rey) 5 > 0 1 X u (Qo,>,fí) (qb,0,fí) (<7i,1,fl) (r, u, L) <71 (<7i,1,fl) (r, U, L) r (so, >, R) (/", 1, (r, X, L) So (si, X, fí) (qfrey,-,-) (s0,X, R) [Qacc, ~) —) s^ (si,0,fí) (r, X, L) (si, X, fl) (Qrey, -) o o o 1 1 1 u u IB102 Automaty, gramatiky a složitost, 28.11.2016 5/28 Asymptotická analýza Motivace ■ jaká složitost je lepší: 6n nebo n2 + 5? ■ na delších vstupech jsou výpočty obvykle delší ■ zajímá nás chování pro n -> oc ■ konstantní faktor neuvažujeme (výpočet lze zrychlit) IB102 Automaty, gramatiky a složitost, 28.11.2016 6/28 Asymptotická analýza Motivace Věta. Pro každý deterministický úplný TM M a pro každé m > 1 lze zkonstruovat deterministický úplný TM M' tak, že L(M) = L(M') a m Důkaz. IB102 Automaty, gramatiky a složitost, 28.11.2016 (9-notace Definice. Nechť f,g : N0 K+ jsou funkce. Řekneme, že g je asymptotická horní závora pro f, a píšeme f e 0(g) nebo f = jestliže existují konstanty c,í)0gN takové, že Vn > n0 : ř(n) < cgr(n). Příklad. 15n3 + 3A72 + 11n + 7 IB102 Automaty, gramatiky a složitost, 28.11.2016 8/28 Počítání s (9-notací ■ logaritmy: O(\og n) ■ sčítání: G(n3) + O(n) ■ mocniny: 2°^ IB102 Automaty, gramatiky a složitost, 28.11.2016 9/28 Příklad TM M rozhodující {0^1 ^ | k > 0} lze popsat i takto: □ Zjistí, zda vstup obsahuje nějakou 0 za 1. Pokud ano, zamítne. H Dokud je na pásce nějaká 0, projíždí pásku a vždy škrtne jednu 0 a jednu 1. Pokud se nepovede k nějaké 0 najít 1, zamítne. B Pokud po vyškrtání všech 0 zbude na pásce nějaká 1, zamítne. Jinak akceptuje. IB102 Automaty, gramatiky a složitost, 28.11.2016 10/28 Deterministické časové složitostní třídy problémů časová složitost problému = nejmenší časová složitost, s jakou lze daný problém rozhodnout Definice. Každá funkce f: N0 -> K+ definuje (deterministickou) časovou složitostní třídu problémů TIME(/r(n)) = {/_ | /_je rozhodovaný nějakým deterministickým jedno- nebo vícepáskovým TM M s časovou složitostí TM(n) = 0(f(n))}. IB102 Automaty, gramatiky a složitost, 28.11.2016 11/28 Příklad L = {Okj\k \k>0} ■ ukázali jsme jednopáskový det. TM rozhodující L v čase 0(n2) ■ existuje jednopáskový det. TM rozhodující L v čase O(n\og n) ■ neexistuje jednopáskový det. TM rozhodující L s menší složitostí ■ existuje dvoupáskový deterministický TM rozhodující L v čase O(ri), tedy L je ve třídě TIME(n) IB102 Automaty, gramatiky a složitost, 28.11.2016 12/28 Vliv výpočetního modelu ■ na rozdíl od vyčíslitelnosti, ve složitosti na výpočetním modelu zaleží ■ rozdíl je i mezi jednopáskovým a dvoupáskovým deterministickým TM ■ jaký model zvolit? ■ je volba deterministického vícepáskového TM správná? ■ rozdíly jsou u běžných sekvenčních deterministických výpočetních modelů poměrně malé ■ např. RAM (random-access machine) pracující v čase f(n) lze převést na vícepáskový deterministický TM pracující v čase 0(ř3(A7).(ř(A7) + A7)2) ■ nedeterminismus přináší výrazný rozdíl IB102 Automaty, gramatiky a složitost, 28.11.2016 13/28 Převod vícepáskového TM na jednopáskový Věta. Pro každý vícepáskový deterministický TM pracující v čase f(ri) > n lze sestrojit ekvivalentní jednopáskový deterministický TM pracující v čase 0(f2(n)). Důkaz. □ neprázdný obsah k pásek a polohy hlav zapíšeme za sebe na 1 pásku O(n) Q simulace jednoho kroku ■ zjistit informace pod hlavami = projít pásku, každá původní páska má max. f (n) neprázdných polí O (f (n)) m provést krok, zapsat nové symboly a posunout hlavy (případně přidat další políčka na původní pásky odsunutím obsahu dalších pásek, max. k políček) O (f (n)) B simulujeme f(n) kroků -> celkem O(n) + 0(f2(n)) □ IB102 Automaty, gramatiky a složitost, 28.11.2016 14/28 Časová složitost nedet. Turingova stroje Definice. Nechť M je úplný nedeterministický Turingův stroj se vstupní abecedou Z. Pro každé i^gF definujeme (m(w) jako počet kroků nejdelšího výpočtu stroje M na vstupu w. Časová složitost stroje M je pak funkce TM : N0 N definovaná vztahem TM(ri) = max{ŕM(i/i/) | w e Tn}. IB102 Automaty, gramatiky a složitost, 28.11.2016 15/28 Nedeterministické časové složitostní třídy problémů Definice. Každá funkce f: N0 -> K+ definuje (nedeterministickou) časovou složitostní třídu problémů NTIME(/r(n)) = {L \ L je rozhodovaný nějakým nedeterministickým jedno- nebo vícepáskovým TM M s časovou složitostí TM(n) = O (f (n))}. Z definic plyne TIME(ŕ(n)) c NTIME(ŕ(n)). IB102 Automaty, gramatiky a složitost, 28.11.2016 16/28 Převod nedeterministického TM na deterministický Věta. Pro každý nedeterministický jednopáskový TM pracující v čase f(ri) > n lze sestrojit ekvivalentní deterministický jednopáskový TM pracující v čase 2°(fW\ Důkaz. Nedet. TM M, který má z každé konfigurace max. k přechodů, simulujeme 3-páskovým deterministickým strojem, který prohledává strom výpočtů M do šířky. Pro každý uzel provedeme znovu výpočet z iniciální konfigurace. Strom výpočtů má hloubku nejvýše f(n) a tudíž má nejvýše kf^ listů a méně než 2 • kfW uz|ů. -> 0(kf^) uzlů Simulace výpočtu do jednoho uzlu zabere nejvýše 0(f{rí)) kroků. 3-páskový stroj tedy pracuje v čase 0(f(ri) • kf^) = 2°VW\ Převod na jednopáskový det. stroj: (2°^)2 = 2°^^ = 2°^\ □ IB102 Automaty, gramatiky a složitost, 28.11.2016 17/28 Nejvýznamnější časové složitostní třídy deterministické nedeterministické P = PTIME = U/cGNTIME(^) NP = IJ/cgn NTIME(n/c) EXPTIME = U^GNTIME(2n/í) NEXPTIME = [jkeN NTIME(2n/í) ■ z definic a předchozí věty plyne: P c NP c EXPTIME c NEXPTIME ■ běžné deterministické sekvenční modely výpočtu lze mezi sebou převádět s polynomiálním nárůstem časové složitosti =4> definice P a EXPTIME nejsou citlivé na volbu modelu ■ EXPTIME je obvykle složitost algoritmů řešících problém hrubou silou ■ Cook-Karpova teze P obsahuje právě všechny prakticky řešitelné problémy. IB102 Automaty, gramatiky a složitost, 28.11.2016 18/28 Vztah P a N P P = NP ■ asi nejznámější otevřený problém teoretické informatiky ■ věří se, že platí P c N P ■ důsledky do počítačové bezpečnosti ■ Clay Mathematics Institute (CMI) vypsal 1.000.000 USD za řešení IB102 Automaty, gramatiky a složitost, 28.11.2016 19/28 Příslušnost problémů v P ■ stačí ukázat, že problém je řešitelný v polynomiálním počtu kroků a že každý krok je implementovatelný v polynomiálním čase ■ kódování/dekódování objektů O do slov (O) musí být proveditelné v polynomiálním čase ■ příklad vhodného kódování: reprezentace grafu maticí sousednosti ■ příklad nevhodného kódování: reprezentace sekvence číslic unárním zápisem čísla IB102 Automaty, gramatiky a složitost, 28.11.2016 20/28 Problém existence cesty Problém existence cesty je problém rozhodnout, zda v daném orientovaném grafu G existuje cesta z s do ŕ. PATH = {(G, s, t) | G je orientovaný graf obsahující cestu z s do ŕ} Věta. PATH e P. Důkaz. Postupně spočítáme uzly dosažitelné z s. D označ uzel s H dokud lze označit nový uzel opakuj: projdi všechny hrany v G a označ každý uzel, do kterého vede hrana z označeného uzlu B je-li t označeno, akceptuj; jinak zamítni Celkem 0(ri) kroků (n je počet uzlů v G), každý lze provést v polynomiálním čase. IB102 Automaty, gramatiky a složitost, 28.11.2016 Problém Hamiltonovské cesty Hamiltonovská cesta = cesta procházející každým uzlem právě jednou Problém Hamiltonovské cesty je problém rozhodnout, zda v daném orientovaném grafu G existuje Hamiltonovská cesta z s do t. HAMPATH = {(G, s, ř) | G je orientovaný graf obsahující Hamiltonovskou cestu z s do ř} IB102 Automaty, gramatiky a složitost, 28.11.2016 22/28 Problém Hamiltonovské cesty Věta. HAMPATH e N P. Důkaz. ■ Hamiltonovská cesta v grafu G s n uzly má délku n - 1 ■ Hamiltonovskou cestu budeme nedeterministicky hádat O začni budovat cestu z uzlu s H (a? - 1)-krát opakuj: nedeterministicky vyber hranu vedoucí z posledního uzlu cesty a přidej ji na konec cesty B je-li t poslední uzel cesty a žádný uzel se neopakuje, akceptuj; jinak zamítni ■ každý výpočet má O (h) polynomiálních kroků ■ Hamiltonovská cesta existuje <=^> existuje akceptující výpočet □ IB102 Automaty, gramatiky a složitost, 28.11.2016 23/28 Polynomiální redukce Definice. Nechť A c z* a B c 0* jsou jazyky. Řekneme, že A se polynomiálně redukuje na 6, píšeme /4