Vztah teorie vyčíslitelnosti a teorie složitosti IB102 Automaty, gramatiky a složitost, 7.12.2015 1/29 Č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, 7.12.2015 2/29 Č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é w 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(n) = max{ŕM(i/i/) | w e Tn}. Říkáme, že M pracuje v čase TM(n). IB102 Automaty, gramatiky a složitost, 7.12.2015 3/29 Příklad M = ({, □}, >, u, S, q0l qacc, qrej) S > 0 1 u qo (Qo,>,R) ( ") (qrej, ~, -) ( ") IB102 Automaty, gramatiky a složitost, 7.12.2015 4/29 Příklad M = ({q0, q^, r, s0, ^, qacc, qrej}, {0,1}, {0,1, X, >, □}, >, u, 6, q0, qacCl qrej) s > 0 1 X u qo (qo,0,R) (<7i,1,fl) (r, u, Z.) (qrej, -, -) (<7i,1,fl) (r, u, L) r (so, >, R) (/", 1, (r, X, Z.) So (si, X, /?) (Qrey,-,-) (s0,X, R) (qacc, ~, j s^ (si,0,fí) (r, X, Z.) (si, X, fl) (qrej, ~, -) o o o 1 1 1 u u IB102 Automaty, gramatiky a složitost, 7.12.2015 5/29 Asymptotická analýza 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, 7.12.2015 6/29 Asymptotická analýza 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, 7.12.2015 □ 7/29 (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 O(g) nebo f = 0(gr), jestliže existují konstanty c,í)0gN takové, že Vn > n0 : < cgf(n). Příklad. 15n3 + 3n2 +11/7 + 7 IB102 Automaty, gramatiky a složitost, 7.12.2015 8/29 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, 7.12.2015 9/29 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, 7.12.2015 10/29 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, 7.12.2015 11/29 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(n), tedy/.je ve třídě TIME(n) IB102 Automaty, gramatiky a složitost, 7.12.2015 12/29 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(f3(n).(f(n) + n)2) ■ nedeterminismus přináší výrazný rozdíl IB102 Automaty, gramatiky a složitost, 7.12.2015 13/29 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í -» 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) -» O (f (n)) B simulujeme f (n) kroků -> celkem O (n) + 0(f2(n)) □ IB102 Automaty, gramatiky a složitost, 7.12.2015 14/29 Č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(n) = max{ř^(i^) | w e Tn}. IB102 Automaty, gramatiky a složitost, 7.12.2015 15/29 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) = 0(f(n))}. Z definic plyne TIME(ŕ(n)) c NTIME(ŕ(n)). IB102 Automaty, gramatiky a složitost, 7.12.2015 16/29 Převod nedeterministického TM na deterministický Věta. Pro každý nedeterministický jednopáskový TM pracující v čase f(rí) > n lze sestrojit ekvivalentní deterministický jednopáskový TM pracující v čase 2°^f^\ 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 ■ kŤ^ uzlů. -> 0{kf^) uzlů Simulace výpočtu do jednoho uzlu zabere nejvýše 0(f(ri)) kroků. 3-páskový stroj tedy pracuje v čase 0(f(rí) • kf^) = 2°^\ Převod na jednopáskový det. stroj: (2°^)2 = 2°(2f(n» = 2°^\ □ IB102 Automaty, gramatiky a složitost, 7.12.2015 17/29 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, 7.12.2015 18/29 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, 7.12.2015 19/29 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, 7.12.2015 20/29 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č stav s H 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 ř označeno, akceptuj; jinak zamítni Celkem O (n) kroků (n je počet stavů G), každý lze provést v polynomiálním čase. IB102 Automaty, gramatiky a složitost, 7.12.2015 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, 7.12.2015 22/29 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 D začni budovat cestu ze stavu 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, 7.12.2015 23/29 Problem složených cisel Problém složených čísel je problém rozhodnout, zda je dané číslo x složené, tedy součinem dvou čísel větších než 1. COMPOSITES = {(x) | x = pq pro nějaká přirozená čísla p, q > 1} Věta. COMPOSITES e N P 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, 7.12.2015 24/29 Polynomiální redukce Definice. Nechť A c z* a B c 0* jsou jazyky. Řekneme, že A se polynomiálně redukuje na fí, píšeme /A