Príklady P=polynomiální čas 5. Výpočetní složitost Jan Paseka Ústav matematiky a statistiky Masarykova univerzita 18. října 2021 Příklady • Úvod • Násobení o Permanenty • Třídění • Prvočíselnost • Největší společný dělitel a Euklidův algoritmus Fl Důkaz toho, že existují nerozhodnutelné problémy a nevyčíslitelné funkce, je jedním z největších výdobytků v této oblasti. Fl Důkaz toho, že existují nerozhodnutelné problémy a nevyčíslitelné funkce, je jedním z největších výdobytků v této oblasti. Šifrovací systém, jehož dešifrování je založeno na výpočtu nevyčíslitelných funkcí, by měl výhodnou pozici. Můžeme však snadno ověřit, že takovéto zbožné přání nemůže být splněno: všechny takovéto systémy jsou konečné a tedy mohou být narušeny prověřením všech možností. Fl Důkaz toho, že existují nerozhodnutelné problémy a nevyčíslitelné funkce, je jedním z největších výdobytků v této oblasti. Šifrovací systém, jehož dešifrování je založeno na výpočtu nevyčíslitelných funkcí, by měl výhodnou pozici. Můžeme však snadno ověřit, že takovéto zbožné přání nemůže být splněno: všechny takovéto systémy jsou konečné a tedy mohou být narušeny prověřením všech možností. Teorie výpočetní složitosti se týká třídy problémů, které lze v principu vyřešit: ale vzhledem k této třídě se teorie pokouší klasifikovat problémy podle jejich výpočetní obtížnosti v závislosti na množství času nebo paměti potřebných pro toto řešení. Porozumění základním pojmům teorie složitosti je podstatné pro kryptografii a v této kapitole se budeme snažit pokrýt podstatu problémů teorie složitosti. Nejprve začněme informálně s několika příklady. Porozumění základním pojmům teorie složitosti je podstatné pro kryptografii a v této kapitole se budeme snažit pokrýt podstatu problémů teorie složitosti. Nejprve začněme informálně s několika příklady. Příklad 1.1 {Násobenípřirozených čísel) Uvažme problém násobení dvou binárních n-bitových čísel x a y. Je-li x = x1 .. .xn ay = y\ ... yn, můžeme provést standardní metodu "dlouhého násobení", která je učena na základní škole následovným způsobem: Porozumění základním pojmům teorie složitosti je podstatné pro kryptografii a v této kapitole se budeme snažit pokrýt podstatu problémů teorie složitosti. Nejprve začněme informálně s několika příklady. Příklad 1.1 {Násobenípřirozených čísel) Uvažme problém násobení dvou binárních n-bitových čísel x a y. Je-li x = x1 .. .xn ay = y\ ... yn, můžeme provést standardní metodu "dlouhého násobení", která je učena na základní škole následovným způsobem: Postupně násobme x čísly y^, y2 atd., posuňme a pak přičtěme výsledek. Každé násobení x číslem y j nás stojí n jednoduchých bitových operací. Podobně sečtení n součinů nám zabere 0(n2) bitových operací. Je tedy celkový počet operací 0(n2). Příklad 1.1 (Násobenípřirozených čísel - pokračování) Můžeme výše uvedené ještě zlepšit? Tj., existuje rychlejší algoritmus v tom smyslu, že provede podstatně méně bitových informací. Přesněji, jsou-li dána 2 n-bitová čísla, n sudé, píšeme x = a2^ + b, y = c2Í + d, pak součin z lze získat pomocí tří násobení \ n-bitových čísel použitím reprezentace z = xy = (ac)2n + [ac + bd-(a- b){c - d)]2Í + bd. P=polynomiální čas Príklad 1.1 (Násobenípřirozených čísel - pokračování) Můžeme výše uvedené ještě zlepšit? Tj., existuje rychlejší algoritmus v tom smyslu, že provede podstatně méně bitových informací. Přesněji, jsou-li dána 2 n-bitová čísla, n sudé, píšeme x = a2% + b, y = c2Í + d, pak součin z lze získat pomocí tří násobení \ n-bitových čísel použitím reprezentace z = xy = (ac)2n + [ac + bd-(a- b){c - d)]2Í + bd. Označíme-li T(n) čas, který nám zabere násobení podle této metody, máme, prože násobení 2n je rychlé, že Příklad 1.1 (Násobenípřirozených čísel - pokračování) Po vyřešení výše uvedené rekurentní nerovnosti obdržíme, že T(n) < Ari093 + Bn, kde A a B jsou konstanty. Příklad 1.1 (Násobenípřirozených čísel - pokračování) Po vyřešení výše uvedené rekurentní nerovnosti obdržíme, že T(n) < Ari093 + Bn, kde A a B jsou konstanty Protože log 3 ~ 1.59, máme k dispozici algoritmus o časové složitosti 0(n1-59) v porovnání se standardním 0(n2) algoritmem. V současnosti má jeden z nejlepších známých algoritmů (Schônhagen, Strassen) složitost 0(nlognloglogn). Uvažujme následující dva výpočetní problémy. Pro každý vstup složený z binární matice A typu n x n chceme vypočítat O determinant matice A, píšeme pak detA, O permanent matice A, píšeme pak per A, permanenent je definován jako kde sčítáme přes všechny permutace tt na množině {1,2,..., n} a au značí {i, j)-tou komponentu matice A. 71 Príklady P=polynomiální čas Uvod Násobení Permanenty Třídění Prvočíselnost Euklides Příklady V Příklad 1.2 (Determinanty a permanenty) Uvažujme následující dva výpočetní problémy. Pro každý vstup složený z binárni matice A typu n x n chceme vypočítat O determinant matice A, píšeme pak detA, O permanent matice A, píšeme pak per A, permanenent je definován jako perA = ^2aUO)a2 7T(2) ... a mr(n) 7T kde sčítáme pres všechny permutace n na množine {1,2,..., n} a a-fj značí {i, j)-tou komponentu matice A. Zdánlivě je permanent mnohem jednodušší funkce matice A než její determinant; jedná se o součet toho samého systému termů, ale bez toho, že bychom dávali pozor na ± znaménka Příklad 1.2 (Determinanty a permanenty - pokračování) Avšak z hlediska výpočetní složitosti platí opak: zatímco determinant je relativně snadná funkce k výpočtu, u permanentu se prokázalo, že se téměř vždy jedná o neobvykle obtížnou záležitost. Příklad 1.2 (Determinanty a permanenty - pokračování) Avšak z hlediska výpočetní složitosti platí opak: zatímco determinant je relativně snadná funkce k výpočtu, u permanentu se prokázalo, že se téměř vždy jedná o neobvykle obtížnou záležitost. Upřesněme výše uvedené (za předpokladu ohraničenosti délky vstupů v naší matici): standardní Gaussova eliminační metoda výpočtu determinantu matice n x n potřebuje 0(n3) bitových operací, přičemž V. Strassen zkonstruoval, který potřebuje 0(nlog27) = 0(n2-81-) bitových operací. 9 Příklad 1.2 (Determinanty a permanenty - pokračování) Redukce exponentu pod hranici log27 se prokázalo být velmi obtížné a jeden z nejrychlejších současných algoritmů (Coppersmith, Winograd)potřebuje 0(n2-3976 •) operací □ s Příklad 1.2 (Determinanty a permanenty - pokračování) Redukce exponentu pod hranici log27 se prokázalo být velmi obtížné a jeden z nejrychlejších současných algoritmů (Coppersmith, Winograd)potřebuje 0(n2-3976 •) operací Snadno je vidět, že všechny vstupy matice musí být načteny a tedy n2 < tdet(n) < Cn2-3976- kde tdet(ri) označuje časovou složitost problému výpočtu determinantu a C je nějaká konstanta. □ s Příklad 1.2 (Determinanty a permanenty - pokračování) Redukce exponentu pod hranici log27 se prokázalo být velmi obtížné a jeden z nejrychlejších současných algoritmů (Coppersmith, Winograd)potřebuje 0(n2-3976 •) operací. Snadno je vidět, že všechny vstupy matice musí být načteny a tedy n2 < tdet(n) < Cn2-3976- kde tdet(ri) označuje časovou složitost problému výpočtu determinantu a C je nějaká konstanta. Pro permanent však oproti výše uvedenému žádný takový algoritmus není znám. Nej rychlejšídoposud známý algoritmus je pouze o něco lepší než sečtení všech n\ termů naší sumy. □ s Příklad 1.3 {Třídění) Předpokládejme, že chceme sestrojit algoritmus, který, obdrží-li na vstupu n celých čísel a^, an, setřídí tyto v rostoucím pořadí. Snadný, téměř instinktivní přístup je následující algoritmus, známý jako Bubblesort. Příklad 1.3 {Třídění) Předpokládejme, že chceme sestrojit algoritmus, který, obdrží-li na vstupu n celých čísel a^, an, setřídí tyto v rostoucím pořadí. Snadný, téměř instinktivní přístup je následující algoritmus, známý jako Bubblesort. Postupně porovnávejme a-i s každým s prvků a2, an. Pro maximální index i takový, že a, < a^ umístěme a-i za a, a obdržíme pak nové uspořádání. Po n- 1 porovnáních obdržíme uspořádání b^ ,...,bn;je okamžitě vidět, že se jedná o vzestupně uspořádaný seznam. Jednoduchý výpočet ukazuje, že k výše uvedenému je třeba 0(n2) porovnání. P=polynomiální čas Príklad 1.3 {Tndeni - pokračování) Poznamenejme, že máme několik rekurzivních algoritmů založených na principu rozděl a panuj tím, že třídíme 2 polovice množiny a pak spojíme setříděné seznamy k sobě, což nám zabere pouze O(nlogn) srovnání. Pro názornost uveďme následující tabulku P=polynomiální čas Príklad 1.3 {Tndeni - pokračování) Poznamenejme, že máme několik rekurzivních algoritmů založených na principu rozděl a panuj tím, že třídíme 2 polovice množiny a pak spojíme setříděné seznamy k sobě, což nám zabere pouze O(nlogn) srovnání Pro názornost uveďme následující tabulku n nlog2n n2 ^300 2500 . 500 ~ 4500 250000 P=polynomiální čas Príklad 1.3 {Tndeni - pokračování) Poznamenejme, že máme několik rekurzivních algoritmů založených na principu rozděl a panuj tím, že třídíme 2 polovice množiny a pak spojíme setříděné seznamy k sobě, což nám zabere pouze O(nlogn) srovnání. Pro názornost uveďme následující tabulku n nlog2n n2 ^300 2500 . 500 ~ 4500 250000 Ovšem, výraz 0(n logrí) může skrýt velké konstantní výrazy, ale tak jako tak se jedná o velký rozdíl, obzvláště proto, že třídění je často používaný algoritmus a velikost seznamů je často velmi velká. Príklad 1.3 (Třídění- pokračování) Jiný fascinující pohled na třídění je ten, že existuje spodní mez stejného řádu pro každý algoritmus založený na třídění. Príklad 1.3 (Třídění- pokračování) Jiný fascinující pohled na třídění je ten, že existuje spodní mez stejného řádu pro každý algoritmus založený na třídění. Často mluvíme o informačně-teoretické spodní mezi, ale nejedná se o nic jiného, než o přímý důsledek pozorování, že každý algoritmus založený na srovnání lze reprezentovat pomocí binání stromové struktury a protože musíme pokrýt všech n\ možných uspořádání, každý takovýto strom musí mít alespoň n\ listů. Příklad 1.4 (Testprvočíselnosti) Bezprostredne se zdá, že testovat, zda přirozené číslo N je prvočíslo, lze vyřešit velmi rychlým a snadným algoritmem: testujeme, zda je N dělitelené 2 nebo nějakým lichým číslem z intervalu [3, Příklad 1.4 (Testprvočíselnosti) Bezprostredne se zdá, že testovat, zda přirozené číslo N je prvočíslo, lze vyřešit velmi rychlým a snadným algoritmem: testujeme, zda je N dělitelené 2 nebo nějakým lichým číslem z intervalu [3, Protože se jedná pouze o\N^ dělení, jedná se o polynomiální algoritmus v proměnné N a tudíž rychlý algoritmus. Příklad 1.4 (Testprvočíselnosti) Bezprostředně se zdá, že testovat, zda přirozené číslo N je prvočíslo, lze vyřešit velmi rychlým a snadným algoritmem: testujeme, zda je N dělitelené 2 nebo nějakým lichým číslem z intervalu [3, Protože se jedná pouze o\N^ dělení, jedná se o polynomiální algoritmus v proměnné N a tudíž rychlý algoritmus. Avšak další úvahy ukazují, že reprezentace čísla N v počítači by byl binární řetězec délky \logN~\ a tudíž, abychom mohli algoritmus na testování prvočíselnosti považovat za rychlý, jeho výpočetní složitost musí být polynomiální v n = \log A/]. Príklad 1.4 (Testprvocíselnosti- pokračování) V současnosti jsou k dispozici algoritmy se složitostí t(N) = 0(ln N) Clnln InN kde c je kladná konstanta. Příklad 1.4 (Test prvočíselnosti - pokračování) V současnosti jsou k dispozici algoritmy se složitostí t(N) = 0(\nN)clnlnlnN, kde c je kladná konstanta. V roce 2002 byl poprvé nalezen M. Agrawalam, K. Neerajem a N. Saxenou deterministický test na prvočíselnost. Jejich test na prvočíselnost měl složitost 0((/ogn)12). Následně Lenstra a Pomeranče představili verzi testu, která běží v čase 0((lognf). Příklady P=polynomiální čas \/00 ásobení Třídění Prvočíselnost Euklides Príklad 1.5 (Nejvetší společný dělitel a Euklidův algoritmus) Uvažujme problém nalezení největšího společného dělitele (nsd) dvou přirozených čísel u a v. Príklady P=polynomiální čas /od ásobení Příklad 1.5 {Největší společný dělitel a Euklidův algoritmus) Uvažujme problém nalezení největšího společného dělitele (nsd) dvou přirozených čísel u a v. Zřejmá metoda je faktorizace obou čísel na prvočísla u = 2U'3U25U3..., v = 2V'3V25V3 pak lze zjistit jejich největší společný dělitel následovně w = nsd(u, v) = 2W'3W25W3 kde Wj = min{uh Vj}. Príklady P=polynomiální čas \/00 ásobení Třídění Prvočíselnost Euklides Príklad 1.5 (Nejvetší společný dělitel a Euklidův algoritmus) Uvažujme problém nalezení největšího společného dělitele (nsd) dvou přirozených čísel u a v. Zřejmá metoda je faktorizace obou čísel na prvočísla u = 2U'3U25U3..., v = 2V'3V25V3 pak lze zjistit jejich největší společný dělitel následovně w = nsd(u, v) = 2W'3W25W3 kde Wj = min{Uj, Vj}. Jedná se však o velmi neefektivní postup. Potřebujeme totiž faktorizovat obě čísla a tento postup nelze rychle provést pro velká přirozená čísla. P=polynomiální čas Príklad 1.5 {Euklidův algoritmus - pokračování) Metoda, jíž tento postup můžeme obejít, je známá jako Euklidův algoritmus. Príklady P=polynomiální čas \/00 ásobení Třídění Prvočíselnost Euklides Príklad 1.5 [Euklidův algoritmus - pokračování) Metoda, jíž tento postup můžeme obejít, je známá jako Euklidův algoritmus. Předpokládejme, že u > v > 0. Pak obdržíme posloupnost dělení: u=aA v + bi, v=a2b^ + b2 bi =a3b2 + b3 0 < fy < v, 0 < b2 < bi 0) či doleva {<—), O změní svůj současný stav z g, na q7. Výpočet Turingova stroje je tedy řízen přechodovou funkcí Control unit Read-write head 0 1 0 0 0 0 1 1 0 1 2-way infinite tape Príklady P=polynomiální čas Třída P Složitost Výpočet Turingova stroje sestává z následujících kroků: reprezentace výpočtu konečným řetězcem xgIJ, kde Z0 = 51 \ {*}, který je umístěn ve čtvercích 1 - n, kde n je počet symbolů obsažených v x, Výpočet Turingova stroje sestává z následujících kroků: O reprezentace výpočtu konečným řetězcem xgIq, kde Z0 = 51 \ {*}, který je umístěn ve čtvercích 1 - n, kde n je počet symbolů obsažených v x, Q odstartování činnosti Turingova stroje z jeho počátečního stavu (obvykle q0) s přepisovací hlavou na čtverci 1 a jeho pokračování se základními operacemi (četní, zapsání a změny stavu) až do doby, kdy stroj skončí v koncovém stavu (qf). Výpočet Turingova stroje sestává z následujících kroků: O reprezentace výpočtu konečným řetězcem xgIq, kde Z0 = 51 \ {*}, který je umístěn ve čtvercích 1 - n, kde n je počet symbolů obsažených v x, Q odstartování činnosti Turingova stroje z jeho počátečního stavu (obvykle q0) s přepisovací hlavou na čtverci 1 a jeho pokračování se základními operacemi (četní, zapsání a změny stavu) až do doby, kdy stroj skončí v koncovém stavu (qf). Výstup stroje M po jeho aplikování na stav x je obsah pásky dosažený v koncovém stavu. Príklady P=polynomiální čas Třída P Složitost Výpočet Turingova stroje sestává z následujících kroků: reprezentace výpočtu konečným řetězcem xgIJ, kde Z0 = 51 \ {*}, který je umístěn ve čtvercích 1 - n, kde n je počet symbolů obsažených v x, Q odstartování činnosti Turingova stroje z jeho počátečního stavu (obvykle q0) s přepisovací hlavou na čtverci 1 a jeho pokračování se základními operacemi (četní, zapsání a změny stavu) až do doby, kdy stroj skončí v koncovém stavu (qf). Výstup stroje M po jeho aplikování na stav x je obsah pásky dosažený v koncovém stavu. Jeden krok výpočtu stroje sestává z jedné akce 1 -3 uvedených výše a délka neboli čas použitý při výpočtu je počet takovýchto kroků. Pokud M označuje nějaký Turingův stroj, označíme tuto dobu ím(x)_. □ľ = s *0 O* Príklady P=polynomiální čas Třída P Složitost Funkce f: Zq Zq je vyčíslitelná pomocí Turingova stroje M, jestliže pro všechna x e Zq> x je vstup pro M, v prípade ukončení výpočtu stroj zastaví s hodnotou f (x) na jeho výstupní pásce. Príklady P=polynomiální čas Třída P Složitost Funkce f: Z£ Z£ je vyčíslitelná pomocí Turingova stroje M, jestliže pro všechna x e Zq, x je vstup pro M, v prípade ukončení výpočtu stroj zastaví s hodnotou f (x) na jeho výstupní pásce. Tedy Turingův stroj je přesná analogie počítače - každý výpočet, který lze vykonat moderním počítačem, lze provést i Turingovým strojem. Příklady P=polynomiální čas Třída P Složitost Funkce f: Z£ Z£ je vyčíslitelná pomocí Turingova stroje M, jestliže pro všechna x e Zq, x je vstup pro M, v případě ukončení výpočtu stroj zastaví s hodnotou f(x) na jeho výstupní pásce. Tedy Turingův stroj je přesná analogie počítače - každý výpočet, který lze vykonat moderním počítačem, lze provést i Turingovým strojem. Ovšem v praxi je konstrukce Turingova stroje schopného i pouze jednoduchých výpočtů velmi časově náročná. Proto byl vyvinut soubor základních Turingových strojů, které provádí odpovídající úlohy. Příklady P=polynomiální čas Třída P Složitost Funkce f: Zq Zq je vyčíslitelná pomocí Turingova stroje M, jestliže pro všechna x e Zq, x je vstup pro M, v případě ukončení výpočtu stroj zastaví s hodnotou f(x) na jeho výstupní pásce. Tedy Turingův stroj je přesná analogie počítače - každý výpočet, který lze vykonat moderním počítačem, lze provést i Turingovým strojem. Ovšem v praxi je konstrukce Turingova stroje schopného i pouze jednoduchých výpočtů velmi časově náročná. Proto byl vyvinut soubor základních Turingových strojů, které provádí odpovídající úlohy. Konstruujeme-li pak složitý Turingův stroj, používáme strojů již dříve zkonstruovaných, podobně jako když používáme subrutiny v obvyklých počítačových programech.^ Príklady P=polynomiální čas Třída P Složitost Můžeme pak formálně definovat časovou složitost. Je-li M Turingův stroj, který zastaví pro všechny vstupy x e Zq, časová složitost Tu ringová stroje M je funkce ím ■ Z+ Z+ určená vztahem = max{ř: existuje xgIq tak, že |x| = n a čas uběhlý strojem M při vstupu x je ŕ}. Príklady P=polynomiální čas Třída P Složitost Můžeme pak formálně definovat časovou složitost. Je-li M Turingův stroj, který zastaví pro všechny vstupy x e Zq, časová složitost Tu ringová stroje M je funkce ím ■ Z+ Z+ určená vztahem = max{ř: existuje xgIq tak, že |x| = n a čas uběhlý strojem M při vstupu x je ř}. Funkce ř je vyčíslitelná v polynomiálním čase nebo má polynomiální složitost, pokud existuje nějaký Turingův stroj M, který vypočte ř a jistý polynom p tak, že ř^(n) < p(n) pro všechna n. Príklady P=polynomiální čas Třída P Složitost Můžeme pak formálně definovat časovou složitost. Je-li M Turingův stroj, který zastaví pro všechny vstupy x e Zq, časová složitost Tu ringová stroje M je funkce ím ■ Z+ Z+ určená vztahem = max{ř: existuje xgIq tak, že |x| = n a čas uběhlý strojem M při vstupu x je ŕ}. Funkce f je vyčíslitelná v polynomiálním čase nebo má polynomiální složitost, pokud existuje nějaký Turingův stroj M, který vypočte ř a jistý polynom p tak, že ř^(n) < p(n) pro všechna n. V praxi většinou neuvažujeme s Turingovým modelem, ale pracujeme na mnohem vyšší úrovni.