Vztah teorie vyčíslitelnosti a teorie složitosti IB102 Automaty, gramatiky a složitost, 1.12.2014 1/30 Č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 Turinguv 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, 1.12.2014 2/30 Časová složitost deterministického Turingova stroje Definice. Nechť M je úplný deterministický (jed n o páskový nebo vícepáskový) Turingův stroj se vstupní abecedou Z. Pro každé wéP definujeme ím{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Í11) = ^3Lx{tM{w) | w g Zn}. Říkáme, že M pracuje v čase TM(n). IB102 Automaty, gramatiky a složitost, 1.12.2014 3/30 Příklad M = {{q0, <7i, qacc, qrej}, {0,1}, {0,1, >, u}, >, u, 6, q0, qacc, qrej) ó > 0 1 u qo (%,>,fl) {qo o,R) (<7i, 1 «) q^ (qrej --) (<7i, 1 «) {qacc, —> —) IB102 Automaty, gramatiky a složitost, 1.12.2014 4/30 Příklad M = {{q0, <7i, r, s0, sA, qacc, qreJ}, {0,1}, {0,1, X, >, u}, >, u, 6, q0, qaCc, qrej) 5 > 0 1 X u qo {qo,>,R) (<7o,0,fl) (<7i,1,fl) (r,u,L) q^ (Qrey,-,-) (<7i,1,fl) (r,u,L) r (sq,>,R) (A",0,L) (r,X, L) s0 (si,X, R) (Qrey,-,-) (so,X, R) {qacc-, ~i ~) Si (si, 0, fl) (r,X,L) (si,X, fl) (qrrey,-,-) o 0 0 0 1 1 1 u u IB102 Automaty, gramatiky a složitost, 1.12.2014 5/30 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 oo ■ konstantní faktor neuvažujeme (výpočet lze zrychlit) IB102 Automaty, gramatiky a složitost, 1.12.2014 6/30 Asymptotická analýza Motivace Věta. Pro každý deterministický úplný TM M a pro každé m > 1 zkonstruovat deterministický úplný TM M' tak, že L(M) = L(M') TM,(n)(gr) nebo f = 0{g), jestliže existují konstanty c, n0 e N takové, že V/i > n0 : f(n) < cg(n). Příklad. 15n3 + 3n2 + 11 n + 7 IB102 Automaty, gramatiky a složitost, 1.12.2014 8/30 ■ logaritmy: O(log n) m sčítání: 0(n3) + O(n) m mocniny: 2°^ IB102 Automaty, gramatiky a složitost, 1.12.2014 Příklad TM M rozhodující {0^1fc | k > 0} lze popsat i takto: □ Zjistí, zda vstup obsahuje nějakou 0 za 1. Pokud ano, zamítne. Q 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, 1.12.2014 10/30 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 -. N ->• N definuje (deterministickou) časovou složitostní třídu problémů TME(f(n)) = {L | L je rozhodovaný nějakým deterministickým TM M s časovou složitostí TM(n) = 0(f(n))}. IB102 Automaty, gramatiky a složitost, 1.12.2014 11/30 Příklad L = {Okj\k \k>0} ■ ukázali jsme jednopáskový det. TM rozhodující L v čase C(/i2) ■ 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(n), tedy L je ve třídě TIME(/i) IB102 Automaty, gramatiky a složitost, 1.12.2014 12/30 Vliv výpočetního modelu ■ na rozdíl od vyčíslitelnosti, ve složitosti na výpočetním modelu záleží ■ 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{f3{n) ■ (f(n) + n)2) ■ nedeterminismus přináší výrazný rozdíl IB102 Automaty, gramatiky a složitost, 1.12.2014 13/30 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(n) > 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) B 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í ->• 0(f(n)) ■ 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) ->• 0(f(n)) Q simulujeme f(n) kroků celkem O(n) + 0(f2(rí)) □ IB102 Automaty, gramatiky a složitost, 1.12.2014 14/30 Časová složitost nedet. Tu ringová stroje Definice. Nechť M je úplný nedeterministický Turingúv stroj se vstupní abecedou Z. Pro každé iveľ 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Í11) = ^3Lx{tM{w) | w g Zn}. IB102 Automaty, gramatiky a složitost, 1.12.2014 15/30 Nedeterministické časové složitostní třídy problémů Definice. Každá funkce f -. N ->• N definuje (nedeterministickou) časovou složitostní třídu problémů NTIME(/:(/i)) = {L | L je rozhodovaný nějakým nedeterministickým TM M s časovou složitostí TM(n) = O (f (n))}. Z definic plyne TIME(f(n)) c NTIME(f(n)). IB102 Automaty, gramatiky a složitost, 1.12.2014 16/30 Převod nedeterministického TM na deterministický Věta. Pro každý nedeterministický jednopáskový TM pracující v čase f(n) > n lze sestrojit ekvivalentní deterministický jednopáskový TM pracující v čase 2°^^\ 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 uzlů. 0{kfW) uzlů Simulace výpočtu do jednoho uzlu zabere nejvýše 0(f(n)) kroků. 3-páskový stroj tedy pracuje v čase 0(f(n) • kfW) = 2°^\ Převod na jednopáskový det. stroj: (2°^)2 = 2°(2ř(n)) = 2°^"». □ IB102 Automaty, gramatiky a složitost, 1.12.2014 17/30 Nejvýznamnější časové složitostní třídy deterministické nedeterministické P = PTIME = UfceNTIME(^) NP = \Jkm NTIME(/i/c) EXPTIME = UfreN TIME(2n,<) NEXPTIME = \Jkm NTIME(2n,<) ■ z definic a předchozí věty plyne: PcNPc 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 =>- 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, 1.12.2014 18/30 Vztah P a NP P = NP ■ asi nejznámější otevřený problém teoretické informatiky ■ věří se, že platí P c NP ■ důsledky do počítačové bezpečnosti ■ Clay Mathematics Institute (CMI) vypsal 1.000.000 USD IB102 Automaty, gramatiky a složitost, 1.12.2014 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, 1.12.2014 20/30 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 t. PATH = {(G, s, ř) | 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. □ označ stav s Q dokud lze označit nový stav 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 O(n) kroků (n\e počet stavů G), každý lze provést v polynomiálním čase. IB102 Automaty, gramatiky a složitost, 1.12.2014 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, t) | G je orientovaný graf obsahující Hamiltonovskou cestu z s do ř} IB102 Automaty, gramatiky a složitost, 1.12.2014 22/30 Problém Hamiltonovské cesty Věta. HAMPATH e N P. Důkaz. ■ Hamiltonovská cesta v grafu Gs n uzly má délku n - 1 ■ Hamiltonovskou cestu budeme nedeterministicky hádat Q začni budovat cestu ze stavu s 0 (n - 1 )-krát opakuj: nedeterministicky vyber hranu vedoucí z posledního uzlu cesty a přidej ji na konec cesty Q je-li t poslední uzel cesty a žádný uzel se neopakuje, akceptuj; jinak zamítni ■ každý výpočet má O (n) polynomiálních kroků ■ Hamiltonovská cesta existuje 1 Věta. COMPOSITES gNP. Důkaz. Zřejmý. "Řešení" problému lze deterministickým TM v polynomiální čase ■ nalézt, je-li problém v P ■ ověřit, je-li problém v NP (pokud nám to řešení někdo dodá) IB102 Automaty, gramatiky a složitost, 1.12.2014 Polynomiální verifikátor Polynomiální verifikátor pro jazyk L je deterministický TM V splňující w g L - existuje polynomiální verifikátor pro L. Důkaz. "=>" Nechť J\f je nedeterministický TM akceptující L v polynomiálním čase. Verifikátor bude pro vstup (w, c) simulovat M na vstupu w a c bude používat k deterministickému výběru z možných přechodů. "* jsou jazyky. Řekneme, že /A se polynomiálně redukuje na B, píšeme A

• A e NP Důkaz. Nechť f je redukce A na B v polynomiálním čase a A^s je TM akceptující B. Stroj A^^ rozhodující A na vstupu w □ spočítá f(w) B spustí Ařs na vstupu a vrátí stejný výsledek jako Ařs Je-li Ařs deterministický, pak je i Ma deterministický. Krok 1 lze provést v polynomiálním čase vzhledem k \ w\, krok 2 v polynomiálním čase vzhledem k |ř(w)|, což je polynomiální i vzhledem k \ w\. Ma tedy pracuje v polynomiálním čase. □ IB102 Automaty, gramatiky a složitost, 1.12.2014 27/30 Polynomiální redukce a složitostní třídy Definice. Nechť C je složitostní třída. Jazyk L nazveme těžký ve třídě C (C-těžký), právě když pro každý jazyk Ľ e C platí Ľ