Vladan Majerech - TSLO Teorie složitosti
Last Modified: 13.2.2020
Index
termíny zkoušek, odkazy, 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.
Termíny zkoušek
Termíny zkoušek budou v pátky ráno, (v místnosti T-204?).
| 24.1.2020 9:00 | se konal |
| 31.1.2020 9:00 | se konal |
| 7.2.2020 9:00 | se konat nebude |
| 14.2.2020 9:00 | se konat nebude |
| 21.2.2019 9:00 | se konat nebude |
Odkazy na obdobné stránky
Moje loňské přednášky. Skripta k přednáškám na MFF (Úvod do složitosti a NP-úplnosti, Složitost a NP-úplnost).
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 na násobení matic. „Odvodili jsme“ Strassenův algoritmus (variantu Winograd varianty) na násobení matic převedením na 7 násobení matic poloviční velikosti. Opět se jednalo o cvičení neobvyklého značení, bez něhož by se důkaz na tabuli nevešel. Rekurence $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 (2 varianty).
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.
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. Hledat medián v lineárním čase se ještě musíme naučit. 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.
Pokud dokážeme medián hledat v lineárním čase, dostáváme $t_v(n,h)\in t_v(n_1,h_1)+t_v(n_2,h_2)+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)$.
K implementaci hledání mediánu (použitého v algoritmu hned na dvou místech) jsme se nedostali.
Přednáška 2
Nejprve jsme se zabývali problémem hledání $k$-tého prvku dle velikosti. Ukázali jsme si rekurence s tím související (a jejich řešení), jak pro neostražitou volbu pivota, randomizovaně pro náhodně voleného pivota tak pro pivota voleného jako medián z mediánů trojic resp. pětic.
Následně jsme se věnovali násobení dlouhých čísel. Začali jsme dvěma variantama Karacuba $O(n^{\log_23})$ algoritmu, pokračovali jsme zobecněním až na $O(f(k)n^{\log_{k}2k-1})$ algoritmus. Již tam jsme řešili problém jak z $2k-1$ dosazení do polynomu řádu $2k-2$ zrekonstruovat příslušný polynom. To jsme použili jako oslí můstek k rychlé diskrétní Fourierově trasformaci. Ukázali, jsme, že při vhodně zvolené množině bodů k dosazování je jak dopředná, tak zpětná transformace velice efektivní (transformace byl přechod z reprezentace polynomů pomocí koeficientů u jednotlivých mocnin do světa hodnot vůči dané množině bodů ... či zpět). Vhodnou bází byly pro $2^k$-tou primitivní odmocninu z 1 $\omega$ její různé mocnicny (v tělese, kde takové odmocniny existují ... komplexní čísla či modulo vhodné prvočíslo). Paralelní dosazení všech mocnin $\omega$ odpovídá násobení Vandermontovy matice pro $\omega$ vektorem koeficientů. Inverzní operace (odsazení?) odpovídá násobení inverzní maticí, která je $1/2^k$ násobkem Vandermontovy matice pro $\omega^{-1}$. Kontrola je jednoduchá, na pozici $i,j$ součinu je těžiště bodů $(\omega^{i-j})^\ell$. Pro $i\not=j$ tvoři tyto body pravidelný několikaúhelník, s těžištěm 0 (pro modulární aritmetiku je nejspíš přesvědčivější součet geometrické řady). Pro $i=j$ body splývají v těžiště 1. Dosud jsme stále na složitosti $\Theta(n^2)$, zásadní urychlení je způsobené extrémním využitím symetrií při násobení implicitní Vandermontovou maticí pro $\omega$. Trik je v tom, že násobení sudými sloupci je možno spočítat zvlášť od násobení lichými sloupci. Součtem mezivýsledků získáme horní polovinu výsledků, zatímco jejich rozdílem dolní polovinu výsledků. Násobení sudými sloupci můžeme interpretovat jako dosazování do polynomů nad $\omega^2$, dosazování do lichých sloupců též jako dosazování do polynomů nad $\omega^2$, ale výsledek musíme pronásobit příslušným $\omega^i$, čímž dostáváme rekurzivní popis Cooley-Tukey algoritmu. Ve výsledku trvá transformace a tedy i násobení pouze $O(n\log n)$.
Dále jsme se krátce věnovali geometrickému algoritmu (jednalo se o Welzlův a Matoušek-Sharir-Welzlův algoritmy) hledání nejmenšího kruhu opsaného dané konečné množině bodů v rovině. Randomizovaně vycházi rekurence lineárně, s rychle rostoucí multiplikativní konstantou v závislosti na velikosti báze určující řešení. V našem případě je báze velikosti nejvýš 3 a tomu odpovídající multiplikativní konstanta je jen 16. Existenci worst case lineárního algoritmu (Megiddo) pomocí vnořených technik prune and search s faktory $15/16$ a dvakrát $3/4$ jsem oznámil bez jakéhokoli bližšího popisu jak prune and search provést.
Ve zbytku hodiny jsme stručně prolétli prohledávání do šířky (BFS) a hloubky (DFS) v explicitních grafech, a naznačili jejich výhody/nevýhody (co se týče zjišťování informací o grafu, BFS teleportace vyžaduje ukládat celý kontext do fronty, zatímco DFS jej může dynamicky udržovat). Pak jsme totéž provedli na implicitních grafech (příkladem byl graf pozic Rubikovy kostky). BFS trpí nedostatkem prostoru, DFS bloudí. Po konci hodiny ... vítězem je iterované prohlubování (IDA), tedy několikanásobné spouštění DFS s postupně větší a větší povolenou hloubkou. U grafů kde hloubkově omezené podgrafy rostou v podstatě geometrickou řadou jsou časy dokončených prohledávání shora odhadnutelné časem posledního dokončeného prohledávání. Proto časová složitost iterativního prohledávání nebude o moc horší než časová složitost BFS. Ještě vhodnější je u implicitních grafů kombinovat původní algoritmy s použitím heuristického odhadu (nejlépe dolního) zbývající nutné vzdálenosti do cíle. Pro Rubikovu kostku IDA* s heuristickým odhadem dle tabulované vzdálenosti na vyřešení rohů resp. 6 vybraných hran (ve 24 otočeních kostky) dokáže najít nejkratší řešení na běžném PC v řádu minut. Po odchodu většiny studentů ... transpoziční tabulky (maximální využitelná paměť, konflikty řešeny přepisováním) k označování již navštívených vrcholů prohledávání urychlují (ale v případě IDA nejsou nutné a v případě DFS pouze snižují pravděpodobnost uvíznutí).
Přednáška 3
Na třetí přednášce jsme se nejprve věnovali prohledávání do hloubky. Začali jsme definicí komponent hranové a vrcholové dvousovislosti a ukázal jsem, jak pomocí ohodnocení low v prohledávání do hloubky můžeme detekovat mosty a artikulace a ž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 popisoval dvouprůchodový algoritmus 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. 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)$.
Zmínil jsem pro prohledávání do šířky kromě hledání nejkratší cesty v explicitním(malém) grafu s hranami ohodnocenými jedničkou znám jen jednu další aplikaci a tou je hledání planárního separátoru v lineárním čase (množina vrcholů velikosti řádově $\sqrt n$ dělící graf na části $A$, $B$ velikostí nejvýš $2n/3$, tak že neexistuje hrana vedoucí mezi $A$ a $B$). Na nalezení planárního separátoru je ale kromě BFS potřeba i DFS.
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é.
Na konci hodiny jsme se oslím můstkem od BFS dostali k hledání nejlacinějších cest v nezáporně ohodnoceném grafu. Dijkstrův algoritmus jsme ale již nestihli přepsat do formy kde jsou explicitně vidět volání potřebné datové struktury. Sice jsem potřebné metody datové struktury zmínil, ale k časovému odhadu chování celého algoritmu jsme se neodstali.
Přednáška 4
Nejprve jsme vyjmenovali zajímavé haldové operace a ukázali, jak by s nimi dopadl rozbor Dijkstrova algoritmu. Rozmysleli jsme si, že lepší popis nedostaneme, protože bychom uměli na základě porovnávání řadit rychleji než je podle důkazu z minulé hodiny možné.
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.
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ů).
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).
V další části hodiny jsem naznačoval, k čemu vede, pokud se zbavíme odkazů na rodiče (tedy ponecháme si odkaz jen v místě kde by byl prázdný ukazatel posledního dítěte). Řády vrcholů jsou pak počítány pouze na základě řádů největších (nejvýše) dvou řádných dětí. Je potřeba udržovat děti ve správném pořadí (první fáze FindMin přidává na konec, druhá na začátek, dítě, jemuž příliš (aspoň $2\times$) klesl řád je pokud se dostane v pořadí mezi děti nejvyšších řádů přesunuto na zařátek). Pokud pro rodiče $p$ největší řád řádného dítěte (před případným jedním poklesem) je $k$ a řád dalšího řádného dítěte (před případným jedním poklesem) není $k-1$, pak řad rodiče $p$ je taky $k$ a rodič je nebezpečný. V opačném případě je rodič bezpečný a má řád $k+1$ (řád neexistujícího dítěte můžeme dodefinovat -1 a není pak potřeba rozebírat okrajové případy). Pokud zakážeme nebezpečného rodiče s kritickým dítětem nejvyššího řádu, bude to sice starost navíc, ale dosáhneme tím $(c,q)$ úzkosti pro $q$ je plastické číslo neboli číslo spojené s Padovan posloupností. Aby udržování invariantů v Padovan haldách fungovalo, je potřeba v/před první fázi/í FindMin zkonvertovat kritické kořeny na nekritické.
Pak jsem ještě naznačil, jak je možno dosáhnout stejné časové složitosti worst case. Filozofií bude, že stupeň každého vrcholu bude implicitně omezen neklesající funkcí, která místo na $n$ bude záviset na $2n-i$, kde $i$ je implicitně udržovaná pozice vrcholu v seznamu všech vrcholů (s výjimkou kořene). Pro vrchol na konci seznamu je tedy omezením funkce s argumentem $n+1$, na začátku je tím argumentem $2n$. Zvětšování $n$ není problém (ať zařaďujeme prvky kamkoli, argumenty funkce pro omezení ostatních prvků mohou jenom vzrůst). Problém je se zmenšováním $n$. Bez tohoto triku by bylo potřeba „řešit“ všechny vrcholy. Takto stačí vyřešit první dva a přeložit je na konec seznamu. Tím zůstanou pro ostatní vrcholy stejná omezení jako před operací.
Ve struktuře jsme schopni udržovat evidenci poruch konstantního počtu druhů, každý druh poruchy se dobře řeší máme-li dva stromy stejného řádu. Pokud tedy udržujeme od každého druhu poruchy počet poruch nepatrně převyšující maximální řád, jsme v konstantním čase takovýto nepořádek schopni udržovat. Ve skutečnosti dochází při řešení poruchy jednoho druhu k potenciálnímu vytvoření jiného druhu, jsme ale schopni vytvořit takovou strategii, která v konstantním čase snižuje celkový počet poruch (byl-li nad prahovou hodnotou). Konkrétní popisy poruch na přednášce nezazněly.
Na konci hodiny 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)$.
Přednáška 5
Na začátku přednášky jsme se věnovali Kruskalovu algoritmu (zpracování předtříděných hran), od naivní implementace s prohledáváním stromů ($O(mn)$) jsme se dostali k naivní datové struktuře pro udržování komponent souvislosti s přímou evidencí komponent jednotlivých vrcholů ($O(m+n^2)$), po udržování stromů odkazů kde jménem komponenty je vrchol odkazující na sebe. Naivní stromy odkazů měly složitost $O(mn)$, ale spojování dle hloubek či velikostí vedlo k omezení vznikajících hloubek na $\log_2 n$ a tudíž ke složitosti $O(m\log n)$. Zkracování cest (tři víceméně rovnocenné metody) v průběhu vyhledávání jmen komponent urychluje budoucí vyhledávání. (Nezaznělo, že při naivním spojování komponent by to stačilo k amortizovanému logaritmickému času na operaci, takže celkem taky k $O(m\log n)$) Společně se spojováním dle hloubek či velikostí dostáváme strukrutu DisjointFindUnion a pro operace nad ní amortizované časy $\alpha(n)$ a celkově pak složitost $O(m\alpha(n))$, kde $\alpha$ je inverzní funkce k Ackermanově funkci $A(n,n)$. Přitom $A(0,n)=2+n$, $A(m,0)=2$ a $A(n+1,m+1)=A(n,A(n+1,m))$ roste tak, že $A(1,n)>2n$, $A(2,n)>2^n$, $A(3,n)>2\uparrow n$ což značí kolikrát musíme iterovat umocňování, obdobně $A(4,n)>2\uparrow\uparrow n$ $\dots$ $A(m,n)>2\uparrow\dots\uparrow n$, kde se v symbolu vyskytuje $m-2$ krát $\uparrow$. (lepší značení by použilo první $\uparrow$ již pro symbol násobení) $\dots$ každopádně $A(n,n)$ roste tak rychle, že v souvislosti s velikostmi vesmíru nemá smysl považovat $\alpha(n)$ za funkci větší než konstanta 6.
Pak jsme se začali bavit o otázce $P=NP$. S tím co je $P$ případně $PF$ nebyl snad problém, u $NP$ jsme dospěli k definici o uhádnutí certifikátu, který ověříme v $P$. Důležité bylo uvědomit si, že certifikát smí být jen polynomiálně velký (takže například nemůžeme při hledání kořenů polynomu postupovat způsobem kdy reálná čísla hádám).
Pak jsme se bavili o výpočetních modelech. Zmínili jsme jak Turingovy stroje (deterministické či nedeterministické), tak pointer machine a RAM. U RAM jsme zvolili model, kde do času operace se bere logaritmus největšího čísla vyskytujícího se v operaci (může se jednat o operand, výsledek operace či adresu operandu či výsledku, v případě nepřímé adresace i adresu, kde je adresa uložena). Logaritmus je zaokrouhlován nahoru na násobek předem zvolené základní jednotky. Naznačili jsme, jak je možno RAM implementovat na Turingově stroji s jen polynomiálním zpomalením. Obdobný trik by se dal použít při simulaci pointer machine a v obou modelech je snadné odsimulovat Turingův stroj. Vždy dostáváme nejvýš polynomiální zpomalení a tudíž dává $P$ stejný smysl, nezávisle na tom v kterém z těchto modelů jej zavedeme.
Shodli jsme se na tom, že nadéle budeme pracovat převážně s Turingovými stroji. Zavedli jsme je ale vícepáskové. Ukázali jsme, že více pásek, speciálně při jejich rozdělení na read only, read write a write only, dává dobrý význam pro prostorovou složitost. Jinak bychom nemohli hovořit o menších než lineárních prostorových nárocích.
Pak jsme ukázali, jak je možno vícepáskový stroj převést na jednopáskový s nárůstem časové složitosti z $t$ na $t^2$. Následně jsme ukázali techniku jak při rozhodnutí posouvat radši pásky po hlavách než opačně organizovat zahušťování a rozřeďování tak, abychom dostali konstantní amortizovanou složitost na práci s každým z $\log t$ bloků. Celkově tak dostáváme nárůst časové složitosti z $t$ na $t\log t$. Tato metoda potřebuje kromě skladovací pásky i pásku pro dočasné použití.
Redukce počtu pásek byl stěžejní krok k vytvoření univerzálního stroje (dostane přechodovou funkci a vstup a spočte to co stroj s danou přechodovou funkcí na daném vstupu).
Přednáška 6
Na přednášce jsme se věnovali $\le_m^P$ převoditelnosti, NP, NP-těžkosti a NP-úplnosti. Dokázali jsme si NP-úplnost problému K, KACHL (v mnoha různých variantách) a SAT (včetně 3-SAT a 3-3-SAT).
Přednáška 7
Na přednášce jsme se věnovali dalším NP-úplným problémům. Barvení grafu 3-mi/$k\ge 3$-barvami, barvení rovinného grafu 3-mi , či rovinného grafu se stupni vrcholů nejvýš 4 3-mi. Dále jsme se věnovali Plesníkovu důkazu NP-úplnosti Hamiltonovské kružnice v rovinném grafu s velmi malými stupni vrcholů. (Předtím jsme probrali vzájemné převody orientovaných či neorientovaných úloh na HK či HC). Následně jsme se věnovali $k$-klikám, $k$-nezávislým množinám a $(n-k)$-vrcholovým pokrytím. Ukázali jsme si jejich vzájemnou převeditelnost a NP-úplnost $k$-NM.
Ke konci hodiny jsme ještě ukázali NP-úplnost problému batoh (při binárním kódování vstupu).
Přednáška 8
Na přednášce jsme o dalších problémech ukazovali, že jsou NP-úplné. Jednalo se o 1 in 3 SAT, celočíselné programování, kachličkování se seznamem kachlíků, kachlíčkování s již položenými, ale nesprávně otočenými kachlíky.
Následně jsme se věnovali aproximacím. Ukázali jsme si 2 a 1,5 aproximaci obchodního cestujícího a následně úplné polynomiální aproximační schéma pro součet podmnožiny (batoh).
Na konci hodiny jsem ukázal, že garance řešení nám nemusí pomoci k nalezení dalšího řešení (na barvení grafu 3mi barvami).
Přednáška 9
Zavedli jsme třídy $(N)Space(f)$, $(N)Time(f)$, definovali jsme konstruovatelné funkce. Ukázali jsme si větu o lineární kompresi a větu o lineárním zrychlení. Ukázali jsme si větu pro odčítání časově konstruovatelných funkcí a to, že funkce které v čase $O(f)$ spočítáme jsou časově konstruovatelné (jsou-li větší než $(1+\varepsilon)n$) Ukázali jsme si uzavřenost prostorově nenáročných operací na skládání, je-li k dispozici alespoň $O(\log n)$ prostoru.
Pak jsme ukázali triviální tvrzení o vztahu definovaných tříd složitosti a vyslovili metavětu o dokazování inkluzí a spočetli si počet konfigurací v prostorem omezeném výpočtu. Metavětu jsme aplikovali na důkaz $NTime(f)\subseteq DSpace(f)$ (je-li $f$ časově konstruovatelná) a na důkaz $NSpace(f)\subseteq\bigcup_c DTime(2^{f(n)+\log n})$. Tím se nám podařilo v „šroubovnici“ inkluzí postupovat do vyšších pater a skončila hodina.
Přednáška 10
Pokračovali jsme v používání metavěty a dokázali jsme Savičovu větu $NSpace(s)\subseteq DSpace((s+\log n)^2)$, za předpokladu prostorové konstruovatelnosti $s$. Pak jsme ukázali, že je $NSpace(s)$ pro prostorově konstruovatelné $s\ge\log n$ uzavřené na doplňky (jsme schopni ke každému stroji vytvořit stroj přijímající doplněk).
Následně jsme ukázali metavětu o jazyku ležícím mezi třídami složitosti. Pak jsme zkonkretizovali předpoklady pro DSpace, NSpace a DTime a dostali jsme tak věty o hierarchii.
Na konci hodiny jsme pomocí prodlužovacího lemma pro DTime naznačili jak ukázat, že $DTime(2^n)\not=Dtime(n2^n)$.
Přednáška 11
Probrali jsme jak Borodinovu větu o mezerách, tak Blumovu větu o kompresi. Následně jsme definovali pro časově omezené výpočty typy nondetermistických stavů a definovali jazyky přijímané a jayzky odmítané takovými stroji. Ukázali jsme si, jak upravit stroj, aby jazyk přijetí byl zachován a doplněk byl jazyk odmítaný takovým strojem. Naznačil jsem složitější typy strojů ve smyslu grafu silných komponent stavů.
Přednáška 12
Dále jsem se věnoval strojům, kde nedeterministické stavy mají definovaný typ (existenční, všeobecný, pravděpodobnostní) a přijímání v daném čase je definováno na základě výpočtu pravděpodobnosti přijetí a pravděpodobnosti odmítnutí. Nejprve jsem ukázal, kolik času a prostoru je potřeba pro deterministickou simulaci výpočtu pracujícího v čase $t$. Z toho ihned vyplynulo, že $\forall\exists? P\subseteq PSpace$.
Následně jsem naznačil, jak iterováním snižovat pravděpodobnosti špatných výsledků randomizované simulace u tříd, kde je garantován odstup od 1/2 v případě pravděpodobnosti (ne)náležení do jazyka. V případě garance nemožnosti nesprávné odpovědi jedním směrem či oběma směry je iterování mnohm snazší.
Pak jsem ještě odbočil k PSpace úplným problémům, speciálně ke střídavě kvantifikované formuli. Ukázal jsem, jak jsme obdobně jako v Savičově větě schopni popsat polynomiálně dlouhou formulí zda existuje sled v grafu konfigurací z počáteční do nějaké přijímací konfigurace. Vzhledem k tomu, že $\forall\exists P$ snadno vyhodnocuje takovéto formule, dostáváme $PSpace\subseteq \forall\exists P(\subseteq PSpace)$.
Pokračovali jsme definicí (polynomiálních) interaktivních protokolů $IP$ s příkladem protokolu pro neizomorfismus grafů. Následně jsme definovali (polyniomiální) hry Artuše s Merlinem $AM\subseteq IP$. Ukázal jsem, že i bez Merlina jsme pomocí $\exists? P$ schopni testovat zda $x\in L$ v případě $x\in AM$, tedy $AM\subseteq \exists? P$.
Následně jsem ukázal jak přetransformovat IP protokol na hru AM, čímž jsme dokázali $IP\subseteq AM$.
Nakonec jsem ukázal hru AM prokazující pravdivost střídavě kvantifikované formule. Bylo kvůli tomu potřeba zavést aritmetizaci formule. Navíc bylo potřeba transformovat formuli do tavru, v kterém mezivýledky aritmetizace budou polynomy malého stupně. Čísla (koeficienty polynomů), která se v aritmetizaci vyskytují mají exponenciální počet bitů, je-li ale formule pravdivá, Merlin může zvolit prvočíslo na jehož zápis stačí polynomiálně bitů, tak aby v příslušné modulární aritmetice byla aritmetizace nenulová. Celý protokol proběhne modulo dané prvočíslo. Merlin má šanci přesvědčit Artuše o pravdivosti nepravdivé formule pouze pokud se během polynomiálního počtu pokusů Artuš (nechtěně) trefí do jednoho z polynomiálně kořenů polynomu (mod p). Při dostatečně velkém p (což Artuš vyžaduje) pak je pravděpodobnost takovéto chyby zanedbatelná. Tím jsme dokázali $PSpace\subseteq AM$, takže se všechny třídy $IP, AM, PSpace, \exists? P$ rovnají. Vzhledem k tomu, že PSpace je uzavřená na doplňky, musí se rovnat i $\forall ? P$.