Vztah teorie vyčíslitelnosti a teorie složitosti IB102 Automaty, gramatiky a složitost, 2.12.2013 1/31 Č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, 2.12.2013 2/31 Č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 (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(h) = max{řM(i^) | w g 5In}. IB102 Automaty, gramatiky a složitost, 2.12.2013 3/31 Příklad M = ({cfo, q^, c/acc, Orej}, {0,1}, {0,1, >, u}, >, u, 6, c/o, qacc, qKj) S > 0 1 u Qo R) (<7acc> 5 -) <7i ( 5 -) IB102 Automaty, gramatiky a složitost, 2.12.2013 4/31 Příklad M = ({, u}, >, u, 5, q0, qacc, qWj) 5 > 0 1 X u qo (Qo,>,Ft) (qb,0,fí) (<7i,1,fl) q^ (qWj,-,-) (<7i,1,fl) r (sq, >, R) (r,0,Z.) (r, X, L) So (si, X, R) (Qrej,-,-) ^, X, fl) (Qacci ~- ~) (st , 0, fl) (/-,X,L) (si, X, R) (Qrej,-,-) > o o o 1 1 1 u u IB102 Automaty, gramatiky a složitost, 2.12.2013 5/31 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, 2.12.2013 6/31 Asymptotická analýza Motivace Věta- Pro každý deterministický úplný TM M a pro každé m > 1 lze zkonstruovat deterministický úplný TM Mr tak, že L(M) = L{M') a Důkaz. IB102 Automaty, gramatiky a složitost, 2.12.2013 (9-notace Definice. Nechť f,g : N0 -> K+ jsou funkce. Řekneme, že g je asymptotická horní závora pro /, a píšeme / e 0(g) nebo / = 0(g), jestliže existují konstanty c, n0 e N takové, že Va7 > r?0 : /(a?) < cgf(/7). Příklad. 15a73 + 3n2 + 1lA? + 7 IB102 Automaty, gramatiky a složitost, 2.12.2013 8/31 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, 2.12.2013 9/31 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, 2.12.2013 10/31 onotace Definice. Nechť /, g : N0 -> K+ jsou funkce. Řekneme, že g roste asymptoticky rychleji než /, a píšeme / e o(g) nebo / = o(g), jestliže lim —^4 = 0. n^oc g[n) Příklad, r? log n = o(n2) Lemma. f = o(g) =4> f = O(g) f = 0{g) ^g£ o{f) IB102 Automaty, gramatiky a složitost, 2.12.2013 11/31 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ů TIME(f(n)) = {L | L je rozhodovaný nějakým deterministickým TM M s časovou složitostí TM(n) = 0(f{rí))}. IB102 Automaty, gramatiky a složitost, 2.12.2013 12/31 Příklad L = {Okj\k | k > 0} ■ ukázali jsme jednopáskový det. TM rozhodující L v čase (D(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/.je ve třídě TIME(a?) IB102 Automaty, gramatiky a složitost, 2.12.2013 13/31 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, 2.12.2013 14/31 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 (D(f2(n)). Důkaz. D 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) -» O (f (n)) B simulujeme f (n) kroků -> celkem O (n) + 0(f2(n)) □ IB102 Automaty, gramatiky a složitost, 2.12.2013 15/31 Č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{ř^(i^) | w e Tn}. IB102 Automaty, gramatiky a složitost, 2.12.2013 16/31 Nedeterministické časové složitostní třídy problémů Definice. Každá funkce /: N -> N definuje (nedeterministickou) časovou složitostní třídu problémů NTIME(/r(/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(/(a?)) c NTIME(/(a?)). IB102 Automaty, gramatiky a složitost, 2.12.2013 17/31 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°^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(ri) a tudíž má nejvýše kf^ listů a méně než 2 • kfW uzlů. -> 0{kf^) 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) • kf^) = 2°VW\ Převod na jednopáskový det. stroj: {2°^f = 2°^f^ = 2°^\ □ IB102 Automaty, gramatiky a složitost, 2.12.2013 18/31 Nejvýznamnější časové složitostní třídy deterministické nedeterministické P = PTIME = U/cGNTIME(a7*) NP = [jkeN NTIME(a7*) 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, 2.12.2013 19/31 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 za řešení IB102 Automaty, gramatiky a složitost, 2.12.2013 20/31 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, 2.12.2013 21/31 Problém existence cesty Problém existence cesty je problém rozhodnout, zda v daném orientovaném grafu G existuje cesta z s to ŕ. 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ů (a? je počet stavů G), každý lze provést v polynomiálním čase. IB102 Automaty, gramatiky a složitost, 2.12.2013 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 to t. HAMPATH = {(G, s, ř) | G je orientovaný graf obsahující Hamiltonovskou cestu z s do ř} IB102 Automaty, gramatiky a složitost, 2.12.2013 23/31 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, 2.12.2013 24/31 Problém složených čísel 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 Dukaz. Zrejmý. "Ř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, 2.12.2013 Polynomiální verifikator Polynomiální verifikator pro jazyk L je deterministický TM V splňující w g L <=^> existuje řetězec c takový, že V akceptuje (w, c) a pracující v polynomiálním čase vzhledem k | w . Věta. L g NP <=^> existuje polynomiální verifikator pro L Důkaz. "=4>" Nechť A/" je nedeterministický TM akceptující L v polynomiálním čase. Verifikator bude pro vstupu (w, c) simulovat J\f na vstupu w ac bude používat k deterministickému výběru z možných přechodů. (t._?! Nechť V je polynomiální verifikator pro L pracující pro vstupy (w, c v čase \ w\k. Nedeterministický stroj J\í nedeterministicky zvolí řetězec c délky nejvýše nk a pak simuluje V na vstupu (w,c). □ IB102 Automaty, gramatiky a složitost, 2.12.2013 26/31 Polynomiální redukce Definice. Nechť A c Z* a fí c 0* jsou jazyky. Řekneme, že /A se polynomiálně redukuje na fí, píšeme /A