Vladan Majerech - TSLO Teorie složitosti
Last Modified: 1.3.2019
Index
termíny zkoušek, přednáška 1, přednáška 2, přednáška 3, přednáška 4, přednáška 5, přednáška 6, přednáška 7, přednáška 8, přednáška 9, přednáška 10, přednáška 11, přednáška 12, přednáška 13
Termíny zkoušek
Termíny zkoušek budou ve čtvrtky ráno, v místnosti T-205.
| 10.1.2019 9:00 | se nebude konat |
| 17.1.2019 9:00 | se nebude konat |
| 24.1.2019 9:00 | se konal |
| 31.1.2019 9:00 | se nekonal |
| 7.2.2019 9:00 | se konal |
| 14.2.2019 9:00 | se nekonal |
| 26.2.2019 12:50 | se konal na MFF UK (MS 302) |
Přednáška 1
Na první přednášce jsme kromě krátkého zmínění $O$, $o$ notace, zmínce o tom, jak se vyjadřuje složitost (bezrozměrné worst case a nezávislé rozměry průměr přes pravděpodobnosti vstupu, randomizace (přes výsledky ovlivněné náhodným generátorem), amortizace (přes různé průběhy jednotlivých operací práce s datovou strukturou)) a vzpomenutí příkladů algoritmů probrali rekurenci rozděl a panuj: $$t(n)\le t(a_1n)+\cdots+t(a_kn)+cn^\alpha.$$ Homogenním řešení rekurence je $n^\beta$, kde $a_1^\beta+\cdots+a_k^\beta=1$, řešení dostáváme ve tvaru $O(n^\alpha+n^\beta)=O(n^{\max\{\alpha,\beta\}})$ v případě, kdy $\alpha\not=\beta$ a $O(n^\alpha\log n)$ v případě $\alpha=\beta$. Na přednášce nezazněl důkaz toho, že to tak skutečně je, to zůstalo na domácí úkol matematickou indukcí. Na přednášce místo toho bylo naznačeno, jak se k uvedeným výsledkům dá dojít. K odvození výsledku vedl v podstatě běžný postup, jen se standardním značením bychom se ztratili v písmenkách, proto jsme psali jen to důležité. Pomohl trik "per partes", kdy mezivýsledky, které již nebudeme dále rozepisovat píšeme do jiné oblasti, než mezivýsledky, které rozepisovat budeme (jen si vedeme „auditní stopu“, která úprava zodpovídá za který mezivýsledek). V našem případě jsou mezivýsledky homogenní a dá se z nich vytknout $cn^\alpha$, stejně tak jsou homogenní části, které budeme rozepisovat. To nám umožňuje v části, kterou budeme rozepisovat vynechat písmenka „t“, „(“, „a“, „n“, „)“ a místo psaní indexů je efektivnější naznačit graficky propojení k rozepisované hodnotě. No a když už se nemusíme zdržovat psaním, tak nám nic nebrání tomu, posčítat výsledky.
Pak jsme se vrhli rovnýma nohama na příklad, využívající uvedenou rekurenci hned čtyřikrát, z čehož třikrát způsobem který je něčím výjimečný. Jednalo se o Kirkpatrick–Seidel algoritmus na hledání konvexního obalu $n$ bodů v rovině, kde výsledkem je $h$-úhelník, čímž je určeno $h$ v časové složitosti $O(n\log h)$ algoritmu. Naznačil jsem, že rychlejší algoritmus než $O(n\log n)$ by musel používat triky, které by umožňovaly řadit „reálná“ čísla v čase lepším než $O(n\log n)$, což například nejde v modelu rozhodovacích stromů. Také jsem naznačil pravděpodobnostní rozložení vstupů, kde se $O(n\log h)$ v průměrném čase chová mnohem lépe než $O(n\log n)$.
Vnější rekurence Kirkpatrick–Seidelova algoritmu je $t_v(n,h)\le t_v(n_1,h_1)+t_v(n_2,h_2)+cn+t_b(n)+t_m(n)$, kde $n_i\le n/2$ a $h_1+h_2+1\le h$ a $t_b(n)$, $t_m(n)$ jsou časy, které dostaneme z dalších rekurencí. Rekurence je neobvyklá parametrem $h$. Přehled případů uvedené rekurence se nedá k určení výsledku využít a musíme si uvědomit jak probíhal výpočet. Když si uvědomíme, že $h$ shora omezuje počet vrcholů v rekurenci, a to, že nevyvážený strom dává menší časovou složitost, než strom vyvážený, můžeme odhadnout hloubku stromu pro nejhorší případ na $O(\log h)$ místo obecného ohadu $O(\log n)$.
Algoritmus hledá úseky konvexního obalu tak, že množinu vstupních bodů dělí geometricky na poloviny a hledá úsek konvexního obalu na rozhraní těchto polovin. Na dělení na poloviny je použit mediánový algoritmus.
Medián hledáme jako $k$-tý prvek pro $k=n/2$ rekurentním algoritmem pomocí pivota. Náhodná volba pivota vede k randomizovaně lineárnímu algoritmu. Chceme-li lineární algoritmus v nejhorším případě, volíme jako pivota aproximaci mediánu. Pokus použít medián mediánů trojic vede k rekurenci $t_m(n)\le t_m(2n/3)+t_m(n/3)+cn$, homogenní řešení je ale $O(n)$ a dostáváme složitost $t_m(n)\in O(n\log n)$. Použití mediánu mediánů pětic vede k rekurenci $t_m(n)\le t_m(7n/10)+t_m(n/5)+cn$, kde již $a_1^\alpha+a_2^\alpha=(7/10)^1+(1/5)^1<1$, takže $\beta<\alpha$ a dostáváme $t_m(n)\in O(n)$.
Zbývá ukázat jak najít horní most, tedy rozhraní konvexního obalu protlého danou polopřímkou. Tam dostaneme rekurenci $t_b(n)=t_b(3n/4)+cn$. Je to zvláštní rozděl a panuj, když dělíme na jedinou část. Říká se mu „prune and search“. V lineárním čase zmenšíme zadání o jednu čtvrtinu, což stačí, vzhledem k tomu, že $a_1^\alpha=(3/4)^1<1$, tak $\beta<\alpha$ a $t_b(n)\in O(n)$.
Vytvoříme dvojice bodů, ty určují směry. Pro polovinu směrů můžeme jeden z bodů zahodit, protože nemůže být na horním mostu. Abychom zjistili pro které směry můžeme jeden z bodů zahodit, najdeme mediánový směr a ten porovnáme se směrem horního mostu. Medián již hledat umíme, porovnání se směrem horního mostu zvládneme přiložením „rovnoběžky“ daného směru a zjištění na které straně od polopřímky se dotkne. Pokud na obou, našli jsme horní most a v rekurenci již nepokračujeme.
Nyní již víme, že $t_v(n,h)\in t_v(n_1,h_1)+t_v(n_2,h_1)+O(n)$, příspěvky každého z nejvýš $O(\log h)$ řádků stromu v nejhorším případě jsou $O(n)$ (se stejnou konstantou), tedy celková složitost je $O(n\log h)$.
Na konci hodiny jsme si uvědomili, že rekurence ve Strassenově algoritmu na násobení matic převedením na 7 násobení matic poloviční velikosti $t(n)\in 7t(n/2)+O(n^2)$ vede ke složitosti $O(n^{\log_27})$ a za domácí úkol bylo rozmyslet si, jak by se obdobný trik mohl použít k násobení dlouhých čísel.
Přednáška 2
Nejprve jsme probrali domácí přípravu (Karacuba), pak jsem ukázal, jak dostat rekurenci pro násobení dlouhých čísel $t(n)\le (2k-1)t(n/k)+c_kn\in c_kn^{\log_k(2k-1)}$, pak jsme probrali Strassenův algoritmus jak (ve variantě s 16 sčítáními (variace na Winogradovu variantu), tak v originální variantě s 18). Pak jsme se vrátili k násobení dlouhých čísel. Inspirace s dosazováním a interpolací již do původního polynomu vypadá neperspektivně. Výběr vhodných hodnot k dosazení naznačuje možnost urychlení jak dosazení, tak inverzní operace (Násobení Vandermondovou maticí všech $2^k$ tých odmocnin z $1$ (v pořadí mocnin jedné primitivní odmocniny) nabízí rekurzivní (Cooley-Tukey) algoritmus, který díky extrémní recyklaci mezivýsledků provede $2^k$ dosazení do polynomu v čase $k2^k$. Inverzní matice je $1/2^k$ krát totéž s řádky a sloupci v opačném pořadí). Tato diskrétní Fourierova transformace stále ještě trpí použitím aritmetiky komplexních čísel, ale v modulární aritmetice již vše zapadá do sebe a algoritmus je efektivní. Jen je potřeba zvolit dostatečně velké vhodné prvočíslo, aby byly rozlišené možné mezivýsledky a aby primitivní odmocnina existovala.
Následně jsme se dostali k tématu prohledávání grafů. Nejprve k obecnému prohledávání velkých (implicitních) grafů. Prohledávání do šířky (BFS), do hloubky (DFS), iterativní prohlubování (IDA), A*, IDA*. Demonstrováno na hledání dopravního spojení. Upozornil jsem na nevýhody jednotlivých metod (paměťová náročnost BFS, zabloudění DFS, IDA těmito nevýhodami netrpí, jen u málo rozvětveného grafu ztrácí efektivitu). Algoritmy s hvězdičkou navíc využívají heuristik. Pak jsem upozornil na výhody (nejkratší cesta BFS, možnost udržovat kontext DFS, oboje IDA). Využívání heuristik bylo demonstrováno i na Rubikově kostce.
Na konci hodiny jsem naznačil jak vypadají stromy prohledávání BFS a DFS a jak vypadají nestromové hrany. U DFS jsem upozornil na preorder a postorder číslování.
Přednáška 3
Na třetí přednášce jsme se nejprve věnovali prohledávání do hloubky. Začali jsme příkladem na nalezení největší vzdálenosti ve stromě s ohodnocenými hranami. Pak jsem definoval komponenty hranové a vrcholové dvousovislosti a ukázal jsem, jak pomocí ohodnocení low v prohledávání do hloubky můžeme detekovat mosty a artikulace (zapoměl jsem upozornit, že můžeme při té příležitosti na zásobníku udržovat vrcholy resp. hrany a při nalezení úzkého hrdla odebrat příslušnou komponentu z vrcholu zásobníku).
Pak jsem zazmatkoval při popisu jednoprůchodového algoritmu na detekci komponent silné souvislosti v orientovaném grafu, ukázal jsem, jak souvisí postorder pořadí s topologickým uspořádáním acyklického orientovaného grafu. Naznačil jsem, jak ve stromě vyhledávat přesnou vzdálenost mezi vrcholy což již vyžaduje $\theta(n)$ velký kontext, takže by prohledávání do šířky bylo extrémně neefektivní (pokud by šlo použít). Kapitolu o lokálních informacích použitelných při prohledávání do hloubky jsem ukončíl konstatováním, že i rovinnost grafu je možno testovat (hledat rovinné nakreslení) pomocí dvouprůchodového prohledávání do hloubky v čase $O(n)$.
Pak jsme se chvíli věnovali rozhodovacím stromům a dolním odhadům. Získali jsme na algoritmy založené na porovnávání odhad $\Omega(n\log n)$, jak pro řazení, tak pro zjištění, zda prvky na vstupu jsou po dvou různé. Chvíli jsme si pohráli s hledáním největší mezery v množině čísel a zjišťováním nejbližší dvojice konečné množiny bodů v rovině (trik s výběrem ze seřazené posloupnosti místo opakovaných řazení podmnožin).
Na konci hodiny jsme se dostali k hledání nejlacinějších cest v nezáporně ohodnoceném grafu. Dijkstrův algoritmus jsme popsali tak, že definoval interface k datové struktuře a z deklarace jejího amortizovaného chování jsme odvodili čas algoritmu $O(m+n\log n)$. Naznačil jsem, jak v případě zdola omezených cen hran kladnou konstantou je možno vybírat minimální prvek až na toleranci, což (Thorup) může vést k asymptoticky ještě efektivnějšímu algoritmu.
Přednáška 4
Nejprve jsme vyjmenovali zajímavé haldové operace. Pak jsme haldy odvozovali na základě principu drahého porovnávání. Postupně jsme přidávali operace, potenciály a invarianty, doplňovali detaily implementace. Začali jsme s rozborem dvojice Insert, FindMin se složitostmi $\bigl(O(1)$, $O(n)\bigr)$. Po zavedení $t_0\Phi_0$ jsme dostali ceny $\bigl(O(1), O(1)\bigr)$. Pak jsme přidali DeleteMin. Bez $t_0\Phi_0$ bychom měli $\bigl(O(1)$, $O(n)$, $O(1)\bigr)$, s $t_0\Phi_0$ pak $\bigl(O(1)$, $O(1)$, $O(n)\bigr)$. Lineární složitost se dá preventovat pokud zajistíme invariant $(c,q)$ úzkosti. Tím se nám zkomplikuje FindMin (musíme porovnávat stromy stejného řádu, pokud to jde). Dostaneme pak složitosti $\bigl(O(1)$, $O(\log n)$, $O(n)\bigr)$, ale s potenciálem $t_0\Phi_0+t_1\Phi_1$ pak $\bigl(O(1)$, $O(\log n)$, $O(\log n)\bigr)$. Rozšířením potenciálu $t_0\Phi_0+t_1\Phi_1+t_2\Phi_2$ přeorganizujeme ceny na $\bigl(O(1)$, $O(1)$, $O(\log n)\bigr)$ což nám pro Binomiální haldy vyhovuje. Složitost máme v nejméně často používané operaci a dostáváme $O(n\log n)$ pro řazení na základě porovnávání, což víme, že je optimum.
Následně přidáme Decrement. Triviální implementace vede k $\bigl(O(1)$, $O(1)$, $O(n), O(1)\bigr)$, protože se rozbije invariant $(c,q)$ úzkosti. Snižování řádů všem vrcholům na cestě ke kořeni vede k $\bigl(O(1)$, $O(1)$, $O(\log n), O(n)\bigr)$. Značkování kritických vrcholů a omezení aktualizace řádů jen na cestu dokud jsou vrcholy kritické (s odstraňování kritičnosti uvnitř cesty) vede také ke složitostem $\bigl(O(1)$, $O(1)$, $O(\log n), O(n)\bigr)$ s tím, že invariant úzkosti funguje pro jiná $c,q$. Vůči potenciálu $t_0\Phi_0+t_1\Phi_1+t_2\Phi_2+t_3\Phi_3$ dostáváme výsledné $\bigl(O(1)$, $O(1)$, $O(\log n), O(1)\bigr)$. Vzhledem k tomu, že nyní invariant úzkosti garantuje minimální velikost stromu řádu $k$ rovnou Fibonacciho číslu $F_k$, říká se těmto haldám Fibonacciho.
Nevýhodou Fibonacciho hald vůči Binomiálním je nutnost udržovat odkazy směrem ke kořeni a seznamy „sourozenců“ musí umožňovat odstraňování libovolného prvku v konstantním čase (dva odkazy místo jednoho). Navíc interface musí při vkládání prvku vracet odkaz, pomocí něhož může v budoucnu vnější svět na prvek ukazovat. Bezpracně dostáváme rozšíření o operaci Delete v ceně $O(\log n)$. V případě, kdy již s haldou nechceme pracovat, můžeme uvolnit paměť v čase (a ceně) $O(n)$, místo abychom plýtvali časem na posloupnost Delete(Min).
Algoritmicky netriviální je pouze operace FindMin, kde si musíme dát pozor, abychom v první fázi detekovali stromy stejných řádů efektivně, a abychom v přechodu do druhé fáze dostali seznam stromů efektivně (čas omezený počtem stromů).
Při snižování řádů si musíme dát pozor, abychom nevytvořili stromy záporného řádu (možnou variantou je při odznačování kritických vrcholů vytvářet další typ vrcholů a na novém typu ukončovat snižování řádů).
Pak jsme si ukázali použití hald ve Fredman-Tarjanově algoritmu na hledání minimální kostry. Trik je v tom, rozdělit výpočet na fáze které mohou trvat nejvýš $O(m)$. To nám dá odhad na velikost haldy, při které již nesmíme volat DeleteMin(), pěstujeme tak stromy dokud nepřirostou k jinému, neskončí nebo nepřekročíme mezní velikost. Pouze v případě překročení velikosti přidělujeme vrcholům stromu nové číslo. Na konci fáze probereme hrany lexikograficky seřazené (řadíme přihrádkově v čase $O(m)$) podle čísel stromů a pro každou dvojici stromů ponecháme nejvýš jednu hranu (minimální), která je spojuje. V další fázi stromy vystupují v roli vrcholů, a odhad na přípustnou velikost haldy vzroste na $2^t$, kde $t$ je odhad z předchozí fáze. Nejpozději ve chvíli, kdy je číslo fáze větší než $\log^* n$, určitě nedojde k překročení velikosti haldy a fáze skončí nalezením kostry. Dostali jsme tak algoritmus složitosti $O(m\log^* n)$.
Ve zbytku hodiny jsme se věnovali Kruskalovu algoritmu a datové struktuře vhodné pro implementaci jednoho kroku. Pro Disjoint Find Union jsme stihli popsat možné efektivní implementace, věděli jsme, že hloubky vznikajících stromů při správném způsobu spojování jsou nejvýš $\log_2 n$. Jak se na ceně projeví zkracování cest jsme neanalyzovali, pouze jsem naznačil, co je Ackermanova funkce a k ní diagonální inverzní $\alpha(n)$. Bez analýzy jsem prohlásil, že cena jednotlivých operací s DFU je $O\bigl(\alpha(n)\bigr)$. Přitom $\alpha(n)$ pro čísla odpovídající Fyzikálním veličinám nikdy nepřekročí hodnotu $6$. Přesnější rozbor, pro provedení $m$ operací místo $O\bigl(m\alpha(n)\bigr)$ uvádí $O\bigl(m\alpha(n,m)\bigr)$ pro inverzní funkci zahrnující dva argumenty a v případě, kdy například $m=\Omega(n\log n)$, vychází $\alpha(m,n)\in O(1)$ nezávisle na gigantičnosti $n$. Dostaneme-li hrany předem seřazené, případně je možno je v čase $o(m\log^* n)$ seřadit, vychází dobře implementovaný Kruskalův algoritmus lépe než Fredman-Tarjanův. V opačném případě řazení hran v předvýpočtu trvá déle než celý Fredman-Tarjanův algoritmus.
Přednáška 5
Na páté přednášce jsem se vrátil k hledání silně souvislých komponent a jako na delší dobu poslední zapomněnku jsem ukázal randomizovaný algoritmus na hledání nejmenšího kruhu obsahující danou konečnou množinu bodů v rovině. Dostali jsme lineární složitost.
Pak jsem začal hovořit o P, NP a PF. Naznačil jsem co to jsou nedeterministické stroje přijímající v polynomiálním čase, a jak jejich přijímání souvisí s polynomiálně dlouhými certifikáty a deterministickými stroji přijímajícími v polynomiálím čase. Povídali jsme si o tom, jaké komplikace by přinášelo definovat funkce počítané nedeterministickými stroji, trošku jsme nakoukli pod pokličku možnosti zavedení jiných než existenčně nedeterministických strojů. Také jsme si trochu povídali o výpočetních modelech (RAM, Turingovy stroje).
Uvědomili jsme si, že polynomy jsou uzavřené na skládání, definovali jsme polynomiální transformaci $\le^P_m$ a uvědomili jsme si, že je tranzitivní, ale není antisymetrická. Pak jsme pro obecnou množinu $C$ jazyků pomocí $\le^P_m$ definovali pojem $C$-těžkého jazyka a následně $C$-úplného jazyka. Speciálně pro NP jsme tak dostali pojmy NP-těžkot a NP-úplnost.
Na konci hodiny jsme ukázali, že jazyk $K^{NP}=\{\langle x,1^t,M\rangle\mid \hbox{nedeterministický stroj $M$ přijme v čase $t$ vstup $x$}\}$ je NP úplný. Potřebovali jsme k tomu věřit, že existuje univerzální nedeterministický stroj schopný simulovat libovolný nedeterministický stroj s polynomiálním zpomalením.
O existenci NP-úplného problému již tedy víme, problémům z praxe je ale na hony vzdálený. Na dalších hodinách si řekneme o praktičtějších NP-úplných problémech.
Přednáška 6
Na začátku hodiny jsem krátce připomenul, co je to NP, NP-těžkost a NP-úplnost. Pak jsem ukázal NP-úplnost kachličkování. Následně jsme si hráli s tím, jak udělat kachličkování přirozenější a dospěli jsme k variantě s jednobarevným obvodem, kde můžeme kachlíky otáčet i převracet. Zároveň jsme si uvědomili, že úloha by byla polynomiální, pokud bychom umožnili otáčet i převracet a navíc by jednobarevná koupelna měla některý rozměr sudý. Důležité bylo, že u variant s jednobarevným obvodem byl rozměr koupelny zadáván unárně. Pokud by byl zadán binárně, bylo by to co hledáme exponenciálně velké vůči velikosti zadání. Pokud bychom nenašli nějaký implicitní popis výsledku, nejspíš by problém vůbec nepatřil do NP. (Nejspíš bychom při velké koupelně oproti velikosti katalogu hledali řešení pro různé velikosti koupelny zhruba velikosti katalogu a snažili se nakombinovat řešení z nich, možná nějaký NP algoritmus existuje, rozhodně ale není triviální.)
Pak jsem nakreslil strom jak budeme ukazovat NP-úplnost problémů. Začali jsme SAT (splnitelností formulí), ukázali jsme jak pomocí SAT řešit kachličkování. Ukázali jsme že délky klauzulí ani počty výskytů proměnných nejsou limitující, že SAT je NP-těžký již pro formule s klauzulemi délky 3, kde se každá proměnná vyskytuje nejvýš třikrát. Taky jsem naznačil, že při omezení na klauzule délky 2 již existuje polynomiální algoritmus. Pro omezení maximálního počtu výskytů proměnných na 2 jsem lehkost nedokazoval. Jdo to polynomiálně? Ukázal jsem, že hezký tvar formule se může hodit při dokazování NP-úplnosti jiných problémů (otázka existence rozestavění daného počtu věží na přípustná pole v kvádru tak, aby žádné dvě neměly shodné dvě souřadnice).
Na konci hodiny jsem ještě ukázal převod SAT na $3$-color. Tak jako v případě většiny dalších problémů bylo potřeba ukázat, že v „programovacím jazyce $3$-color“ jsme schopni definovat booleovskou proměnnou a její negaci a jsme schopni pro dané logické proměnné vytvořit klauzuli (nezávisle na ostatních klauzulích). V případě $3$-color byl vynikajícím „programovacím prostředkem“ trojůhelník. Víme o něm, že jeho vrcholy musí mít v řešení $3$-color všechny $3$ barvy. To nám stačilo k deklarací proměnných i klauzulí. Uvědomili jsme si, že $k$-color pro $k>3$ bude taky NP-úplné a pro $k<3$ je polynomiální. Vzpoměli jsme si na slavnou větu $4$ barev, ze které vyplývá, že pro rovinné grafy je úloha polynomiální i pro $k>3$. To že $3$-color je těžké i pro rovinné grafy ukážeme příště.
Přednáška 7
Přednáška se celá nesla v duchu ukázek transformací a důkazů NP-úplnosti různých problémů. Začali jsme problémem „$1$ in $3$-SAT“. Ukázali jsme, že přirozenou transformací je transformace z $3$-color. Následovalo $3$-color pro rovinné grafy (je možno levé horní křížení hran nahradit podgrafem tak, že je zachována obarvitelnost třemi barvami). Další bylo $3$-color pro rovinné grafy se stupni vrcholů nejvýš $4$ (rovinné nahrazení vrcholu velkého stupně podgrafem zachovávající obarvitelnost třemi barvami, kde nevzniknou vrcholy stupně většího než $4$ a stupeň vrcholu klesne o $2$).
Dále jsme se věnovali $k$-klilkám, $k$-nezávislým množinám a $(n-k)$-vrcholovým pokrytím. Ukázali jsme, že jsou na sebe triviálně transformovatelné (negace hran resp. vybraných vrcholů). Pak jsem ukázal transformaci ze SAT na $k$-nezávislou množinu. ($m+n$ klik, kde $m$ je počet klauzulí a $n$ proměnných, $k=m+n$ vynucuje výběr vrcholu z každé kliky. Kliky literálů dvouprvkové jsou propojeny s klikami klauzulí tak, že literál v klauzuli je spojen hranou s negací téhož literálu v klice literálů. Vybrané vrcholy v klikách literálů korespondují s pravdivě ohodnocenými literály.) Taky jsem bez rozebírání případů naznačil, že je možno převést problém nezávislé množiny velikosti $k$ na problém nezávislé množiny velikosti $k'$ v rovinném grafu (následně i se stupni vrcholů nejvýš $3$).
Pak jsme se věnovali Hamiltonovským kružncím (HK). Ukázal jsem převod ze SAT na hledání HK v bipartitním rovinném grafu, kde jedna partita má indegree $1$ a outdegree $2$, druhá outdegree $1$ a indegree $2$. (Na naplánovanou kružnici jsem přidal dočasná rozvětvení, kde výběr cesty do HK korespondoval s booleovskou proměnnou. Ukázal jsem podgraf, který je možno přidat na dvě takovéto cestičky, který zajišťuje že v HK je právě jedna z cestiček vybrána. Díky této nonekvivalenci jsme schopni k dočasnému rozvětvení $x_i$ připojit dočasné rozvětvení $\neg x_i$. Dalším krokem konstrukce je vytvoření podgrafu pro klauzuli (s aspoň jedním literálem), což bude kružnice připojená k cestičkám literálů tak, že je možno z kružnice projít všechny vrcholy spojky, z cestičky včechny vrcholy spojky i kružnice a taky je možno projít všechny vrcholy spojky při průchodech současně z kružnice i cestičky. Pro klauzuli vytváříme nové dočasné rozvětvení výběr cesty pro HK je po propojení nonekvivalencí s příslušným literálem vynucen volbou cesty v rozvětvení literálu. Pokud zvolíme rozvětvení v literálech tak, že odpovídá pravdivému ohodnocení formule, je možno HK dokreslit v oblasti klauzulí. V opačném případě nevznikne HK, protože se do kružnice nepravdivě ohodnocené kluzule nedá pomocí HK dostat. Naopak, pokud najdeme HK, její průchod rozvětvením literálů nachází ohodnocení literálů splňující formuli. Posledním krokem byla ukázka toho, jak se vyhnout křížení nonekvivalencí. Přidali jsme další dočasná rozvětvení na hrany po nichž HK musí vést. Tato rozětvení je možno propojit nonekvivalentítky tak, že počet křížení nonekvivalentítek kleslo.) Pak jsem ukázal, že pro HK není důležité zda graf je orientovaný (převody tam a zpět rozdělení orientovaného vrcholu na 3 neorientované), že hledání Hamiltonovské cesty (ve variantách podle toho zda jsou specifikovány konce) je stejně těžké jako HK (roztržení orientovaného vrcholu). HK je speciálním případem problému obchodního cestujícího. Ten je proto též NP-úplný (ve variantě, zda existuje cesta dané ceny).
Následoval problém batohu a jeho varianty výběru podmnožiny s daným součtem. Ukázal jsem převod z vrcholového pokrytí velikosti $k$ (Vektorová varianta s výběrem $k$ řádků incidenční matice doplněné libovolným počtem řádků jednotkové matice rozměrů dle počtu hran. Reprezentace v čtyřkové soustavě zaručuje, že nedochází k přenosu mezi řády.).
Nakonec jsem ukázal, proč se nám hodilo, že víme, že HK je těžká i pro grafy se stupňěm vrcholů nejvýš $3$. Díky tomu byl převod HK na Eternity kachlíčkování (dán seznam kachlíků místo katalogu) téměř triviální.
Přednáška 8
Nejprve jsem ukázal o variantě kachličkování, kde máme kachlíky na svých místech, jen je potřeba správně je otočit, že je NP-těžká i v případě, kdy jsou použity pouze dvě barvy.
Pak jsme si ještě hráli s problémem loupežníků dělících si kořist.
Pak jsme se věnovali aproximaci úloh souvisejících s NP-úplnými problémy. Takovými úlohami byl obchodní cestující a součet podmnožiny. (Problém se ptá, zda je daná hodnota dosažitelná, existence polynomiálního algoritmu by nám umožnila půlením intervalu zjistit optimální hodnotu optimalizační verze úlohy.)
Aproximační algoritmus v případě, kdy je daná hodnota dosažitelná, nalezne řešení v intervalu (který je okolo této hodnoty). Pokud hodnota dosažitelná není, může, ale nemusí řešení v uvedeném intervalu najít.
Této definici odpovídalo úplné aproximační schéma pro součet podmnožiny, které pro libovolné zadané $\varepsilon$ dosahovalo časové složitosti $O(n^2/\varepsilon)$ a nacházelo řešení v intervalu $\langle(1-\varepsilon)t,t\rangle$.
Pro aproximaci problému obchodního cestujícího jsme ignorovali cílovou hodnotu a snažili jsme se najít co nejlepší řešení. Ukázali jsme nejprve že umíme nalézt řešení $O$ s hodnotou $h(O)\le 2h(O^*)$, pak jsme ukázali, že umíme heuristiku vylepšit a nalézt řešení s hodnotou $h(O)\le 1.5h(O^*)$, kde $O^*$ je optimální řešení. (Minimální kostra nejprve dvakrát, pak kombinovaná s minimálním perfektním párováním na vybraném podgrafu.)
Pak jsem ještě naznačil, že při řešení NP-těžkých problémů nemusíme házet flintu do žita. V mnoha případech jen malé procento zadání představuje problém a v ostatních případech často snadno řešení nalezneme nebo jeho existenci vyvrátíme. Naznačil jsem „lízátkovou heuristiku“ často umožňující prodloužit cestu při hledání Hamiltonovské cesty v grafech, kde se často vyskytuje mnoho Hamiltonovských cest.
Přednáška 9
V přednášce jsme se seznamovali s Turingovými stroji. Nejprve jsem popsal vícepáskové Turingovy stroje, kde mohly být kromě read/write pásek i read-only (vstupy) a write-only(výstupy).
Pak zazněly věty o lineárním zrychlení a kompresi, ospravedlňující používání $O()$ notace (kromě případu časové složitsti nepřevzšující $(1+\varepsilon)n$).
Pak jsem se zabývali redukcí počtu pásek a ukázali jsme, že je možno simulovat více pásek na jedné pásce s tím, že program běžící v čase $t$ odsimulujeme v čase $O(t^2)$. Použitím amortizačního triku jsme se naučili posouvat obsah pásky v celkovém čase $O(t\log t)$ pro simulovaný výpočet v čase $t$.
Redukci počtu pásek jsme potřebovali pro to, abychom mohli vytvořit univerzální stroj. (Dostane na vstupu program a jeho vstup a dokáže jej simulovat.) Naznačil jsem, jak vyřešit problémy s kódováním libovolně velké pracovní abecedy. Pracovní prostor univerzálního stroje bude konstanta krát větší než simulovaného. Velikost konstanty roste s velikostí stroje. Obdobně čas univerzálního stroje bude konstanta krát $t\log t$, kde $t$ je čas simulovaného stroje. Konstanta opět poroste s velikostí simulovaného stroje.
Nakonec jsem naznačil, že zjistit výsledek nedeterministického výpočtu simulovaného stroje omezeného časem $t$ dokáže jiný univerzální nedeterministický stroj v čase $O(t)$ opět s konstantou rostoucí s velikostí simulovaného stroje.
Přednáška 10
Nejprve jsme zavedli třídy jazyků $DTime(t)$, $NTime(t)$, $DSpace(s)$, $NSpace(s)$ a funkcí $DTimeF(t)$, $DSpaceF(s)$.
Pak jsem vyslovil věty o $O$. Nechť $f_1\in O(f_2)$, pak $DTime(f_1)\subseteq DTime(f_2)$, $NTime(f_1)\subseteq NTime(f_2)$, za předpokladu $f_i(n)>(1+\varepsilon)n$ pro $i\in \{1,2\}$. (viz věta o lineárním zrychlení) a $DSpace(f_1)\subseteq DSpace(f_2)$, $NSpace(f_1)\subseteq NSpace(f_2)$ (bez dodatečného předpokladu). Kvůli důkazu jsem potřeboval vyslovit lemma o konečném počtu výjimek.
Pak jsem vyslovil věty o determinismu jako speciálním případu nedeterminismu. $DTime(t)\subseteq NTime(t)$, $DSpace(s)\subseteq NSpace(s)$.
Pak jsme se dostali konečně k netriviálním tvrzením. Vyslovil jsem metavětu o simulacích. Pokud chceme o jazyku patřícího do $*Space(s)$ dokázat, že patří i někam jinam, hledáme algoritmus, zjišťující, zda je nějaká přijímající konfigurace dosažitelná v grafu konfigurací z počáteční konfigurace. Pokud chceme o jazyku patřícího do $*Time(t)$ dokázat, že patří i někam jinam, hledáme algoritmus, zjišťující, zda je nějaká přijímající konfigurace dosažitelná v stromu výpočtů omezených časem $t$ (typicky zjišťujeme, zda exsituje posloupnost dvojic (display, akce) délky $\le t$, vedoucí z počáteční konfigurace do přijímající, odpovídající výpočtu simulovaného stroje).
Následně jsme aplikovali metavětu na důkaz tvrzení $NTime(t)\subseteq DSpace(t)$. Předpokladem je konstruovatelnost $t$ (časová či prostorová) a $t>(1+\varepsilon)n$.
Dalším důsledkem bylo tvrzení $NSpace(s(n))\subseteq DTime(2^{O(s(n)+\log n)})$. Předpokladem byla prostorová konstruovatelnost $s$. Nejprve jsme spočítali, že počet konfigurací, které se mohou objevit v jednom výpočtu a ovlivňují výsledek přijetí je $2^{O(s(n)+\log n)}$. Konstanta v exponentu závisí na simulovaném stroji a nemáme jak se jí zbavit. Libovolný polynom nad počtem konfigarací dává stále $2^{O(s(n)+\log n)}$, takže libovolný polynomiální algoritmus na prohledávání grafů garantuje platnost tvrzení. Pokud přidáme předpoklad $s(n)\ge \log n$, můžeme pravou stranu zjednodušit na $NSpace(s(n))\subseteq DTime(2^{O(s(n))})$.
Třetím důsledkem bylo tvrzení $NSpace(s(n))\subseteq DSpace((s(n)+\log n)^2)$, opět za předpokladu prostorové konstruovatelnosti $s$. Trikem bylo ověřování dosažitelnosti jedné konfigurace z druhé na $2^k$ kroků. To šlo řešit dvěmi rekurentními voláními s použitím jedné proměnné pro konfiguraci. Podstatné bylo použití stejného prostoru pro obě rekurentní volání. A opět můžeme za předpokladu $s(n)\ge \log n$ zjednodušit na $NSpace(s)\subseteq DSpace(s(n)^2)$ (Savičova věta).
Jako poslední jsem ukázal, jak je možno metavětu použít na vytvoření nedeterministického stroje, který pro libovolný stroj garantující pro $s$ prostorově konstruovatelnou $L\in NSpace(s)$ vytvoří stroj, přijímající ve smyslu $L\in NSpace(s)$, ale takový, že pro slova nepatřící do jazyka nějaká větev výpočtu oznámí NE (přičemž pro slova patřící do jazyka neexistuje větev výpočtu, která by NE oznámila). Stroj tedy můžeme použít k negování výsledků původního výpočtu. Trik byl v tom umět spočítat počet $p_{i+1}$ konfigurací dosažitelných na $i+1$ kroků, za předpokladu, že známe počet $p_i$ konfigurací dosažitelných na $i$ kroků. Výpočet používal nedeterminismus k hádání skutečností umožňující efektivní implementaci, ale všechna nedeterministická rozhodnutí byla ověřena, případně daná větev výpočtu zanikla "FAIL". Všechny odpovědi ANO resp. NE byly garantované.
Přednáška 11
Nejprve jsme v nezapomněnce dokázali věty o hierarchii pro $DTime$, $DSpace$ a $NSpace$. $L=\{1^k0x\mid x$ nepřijme s jedním omezením a univerzální stroj to dokáže zjistit s druhým omezením$\}$. V rámci toho jsme řešili problémy skládání funkcí prostorově omezených výpočtů i problémy s přípravou vstupů u časově omezených výpočtů.
V zapoměnce jsem vzdáleně naznačil, že existuje i Žákova věta hovořící o hierarchii pro $NTime$.
K dalším důkazům nerovnosi tříd speciálně pro $DTime$ (kde v předpokladech věty o hierarchii máme $\log t$ navíc) se hodí prodlužovací lemma.
Následně jsme již nadobro přešli k zapoměnce. Ukázali jsme Borodinovu větu o mezerách a vyslovili Blumovu větu o zrychlení(resp. kompresi). První věta ukazuje, proč je konstruovatelnost funkcí důležitá (měření nekonstruovatelnými funkcemi vede k zdánlivým rozporům s větou o hierarchii). Druhá věta ukazuje, že je dobrý dotaz, zda je možno vyřešit daný problém s danými nároky, ale je špatný dotaz, jaká je optimání složitost na řešení daného problému. (Implementační složitost je v tomto ohledu neoddělitelná od časové resp. prosotrové složitosti.)
Přednáška 12
Na začátku hodiny jsem dokončil náznak důkazu Blumovy věty. Pak jsem se vrátil k interpretaci nedeterministického výpočtu, a v případě časově omezených výpočtů jsem zavedl rozlišení stavů na existenční, všeobecné a pravděpodobnostní. Definoval jsem přijetí slova v takovémto zobecněném modelu. Máme jazyky $L^A$ a $L^R$ odpovídající v kořeni prvděpodobnostem přijetí $a_\rho>1/2$ resp. odmítnutí $r_\rho>1/2$. Pravděpodobnosti přijetí se počítají dle pravděpodobností následníků buď jako $\max, \min$, $\min, \max$ nebo jako vážené průměry. Rozhodli jsme se omezit na výpočty s omezeným větvením na 2 větve se stejnými pravděpodobnostmi. V takovém modelu se nám podařilo ukázat, že libovolný stroj přijímající jazyk $L^A$ jsme schopni modifikovat tak, aby byl jazyk $L^R$ doplňkem jazyka $L^A$.
Definovali jsme typ stroje na základě grafu silně souvislých komponent stavů, tak jak na sebe mohou navazovat, s identifikací, jaké typy stavů se vyskytují v jednotlivých komponentách. Typ můžeme zjednodušit kontrahováním hran, pokud typy jednoho koncového vrcholu jsou obsaženy v typech druhého. Modifikovat stroj tak, aby byl jazyk $L^R$ doplňkem jazyka $L^A$ můžeme při zachování typu stroje.
Naznačil jsem možnost používání názvů tříd ${\cal T}-Time(t)$, kde $\cal T$ je typ. $NTime(t)=\exists-Time(t)$. Obdobně ${\cal T}-P$ a $\exists-P=NP$ Nejobecnější typ obsahuje jediný vrchol zahrnující všechny typy stavů. Definoval jsem $PSpace$ a ukázal jsem, že $\exists\forall?-P\subseteq PSpace$.
Následně jsem pomocí $\exists\to\forall\to\cdots-P$ definoval třídu $\Sigma_k^P$ a pomocí $\forall\to\exists\to\cdots-P$ třídu $\Pi_k^P$. Tyto třídy tvoří tzv. polynomiální hierarchii, počínající $\Pi^P_0=\Sigma^P_0=P$, obsahující $\Sigma^P_1=NP$.
Následně jsem se dostali k pravděpodonostním třídám $?-P=PP\supseteq NP$, a při omezení pravděpodobnosti chyby konstanou menší než $1/2$ (v našem případě $1/3$) jsme dostali třídu $BPP$. V případě jednostranné chyby pak třídu $R\subseteq NP$ a v případě nulové chyby (s neurčitostí menší než 1/2) pak třídu $ZPP$. Naznačil jsem, že na rozdíl od třídy $PP$ jsou třídy $BPP$, $R$ a $ZPP$ užitečné ve smyslu možnosti redukovat chybu resp. neurčitost na exponenciálně malou v polynomiálním čase.
Na konci hodiny jsem ještě ukázal, že $\exists x_1\forall x_2\dots \varphi(x_1,x_2,\dots)$, kde podformule $\varphi$ je v konjunktivně normálním tvaru, je $PSpace$-úplný problém. Střídání kvantifikátorů úzce souvisí s otázkami existence vítězné strategie v antagonistických hrách dvou hráčů. Předtím jsem již naznačil existenci $PP$-úplných problémů.
Přednáška 13
Na přednášce jsme se věnovali výpočetní síle polynomiálně časově omezených výpočtů, s „nespolehlivou dopomocí“. Pro třídu $NP$, když nám „dokazovatel“ předloží hledaný certifikát, můžeme ověřit náležení do jazyka deterministicky v polynomiálním čase.
Pokud u ověřovatele dovolíme používat náhodný generátor, a vyžadujeme separaci $a\lt b$ pravděpodobností příjetí pro slova z jazyka $\ge b$ od pravděpodobnosti přijetí pro slova nepatřící do jazyka $\le a$ (tak jako v případě BPP (např. $a=1/3$, $b=2/3$)), definujeme interaktivní protokoly. Pro $x$ patřící do jazyka musí existovat dokazovatel, který ověřovatele přesvědčí s pravděpodobností aspoň $b$, ale pro nepatřící do jazyka žádný dokazovatle nepřesvědčí oveřovatele s pravděpodobností větší než $a$.
Příkladem interaktivního protokolu je jazyk dvojic neizomorfních grafů. Ověřovatle náhodně vybere graf a vytvoří graf s ním izomorfní. Zeptá se dokazovatele se kterým z původních grafů je nový graf izomorfní. V případě neizomofních grafů to dokazovatel může určit, v opačném případě je pravděpodobnost úspěchu $1/2$. Opakováním testu se snadno dostaneme na požadované pravděpodobnosti.
Mohlo by se zdát, že zatajování výstupů náhodného generátoru je pro interaktivní protokoly klíčové. Speciální třída interaktivních protokolů jsou hry Artuše s Merlinem, kdy Artuš výsledky náhodného generátoru ihned Merlinovi oznamuje.
Hry Artuše s Merlinem odpovídají výpočtům $?\exists$ strojů v polynomiálním čase přijímajícím ve smyslu $BPP$. Odtud víme, že $AM\subseteq PSpace$.
Postupnou transformací obecného protokolu na $AM$ protokol jsem ukázal, že $AM=IP$. (Přidání vygenerovaných náhodných bitů na konec komunikace, jednobitová komunikace, metaprotokol oznamující počet přijímacích větví výpočtu a navigující v stromu vybraných větví výpočtů. Pro slova patřící do jazyka dostáváme pravděpodobnost přijetí 1. Pro slova nepatřící do jazyka dostáváme pravděpodonost přijetí nejvýš $1/2$ (pro $a=1/3$, $b=2/3$). Navigaci je možno provést ve smyslu hry Artuše s Merlinem).
Pak jsem předvedl protokol Artuše s Merlinem pro PSpace úplný problém střídavě kvantifikovaných formulí. Principem byla aritmetizace formule, která je nulová pro nepravdivé formule a kladná pro pravdivé. Vytvoření protokolu komplikuje jak to, že vznikají koeficienty u polynomu, jejichž zápis vyžaduje exponenciálně mnoho bitů, tak to, že stupně proměnných v polynomu jsou exponenciálně velké. Tyto problémy jsou naštěstí řešitelné. Velikosti koeficientů zachrání modulární aritmetika modulo prvočíslo, které Merlin zvolí tak, aby nedělilo aritmetizaci. Se stupni proměnných v polynomu je možno si poradit proložením všeobecných kvantifikátorů existenčními kvantifikátory definujícími dvojníky použitých proměnných. Protokol pak probíhá postupným odstraňováním kvantifikátorů. Vždy zkontrolujeme, že nový polynom po dosazení hodnot $0$ a $1$ koresponduje aritmetizaci před odstraněním kvantifikátoru. Pak zafixujeme hodnotu proměnné náhodnou hodnotou modulo $p$. Aritemtizaci formule bez kvantifikátorů dokáže Artuš spočítat sám a pokud Artuš nenalezne nekonsistenci, prohlásí formuli za pravdivou. Pokud by formule byla nepravdivá a aritmetizace tedy nulová a Artuš nenalezl nekonsistenci, musela by existovat fáze protokolu, po které již se aritmetizace oznamovaná Merlinem shoduje se skutečnou aritmetizací. Poslední fáze, kdy tomu tak nebylo musela končit tím, že ověřovatel pro dosazení trefil kořen rozdílového polynomu. To nastává se zanedbatelnou pravděpodobností a počet fází součet těchto pravděpodobností přes 1/3 nezvýší.
Ve výsledku dostáváme $PSpace=AM=IP$.