Vladan Majerech - NTIN090 Základy složitosti a vyčíslitelnosti

Last Modified: 10.12.2025

Valid HTML 4.01 Strict ... vlastně už jen HTML, ale jaký obrázek?

Index

odkazy, cvičení 1, cvičení 2, cvičení 3, cvičení 4, , cvičení 5,

Pro získání zápočtu z NTIN090 je potřeba získat 10 bodů (2/3 z možných bodů za domácí úkoly zadávané v průběhu semestru). Úkoly budou zadávány brzy po první verzi středečního cvičení a termín na jejich odevzdání bude u úkolu explicitně uveden (nejspíš čt 15:40). Za domácí úkoly odevzdané po termínu je možno získat nejvýš polovinu z uvedených bodů. Úkoly je možno odevzdávat opakovaně (vylepšené verze), v případě opakování nezlepšené verze by byl mírně snížen maximální získatelný počet bodů.

Na domácí úkoly letos použijeme owl. Pokud jste ode mne nedostali e-mail s linkem, tak mne kontaktujte.

Odkazy na obdobné stránky

Cvičení Petra Kučery, moje loňská.

Cvičení 1

Ve čtvrtek v S6 se nepodařilo zprovoznit kameru, takže bohužel cvičení zůstalo bez nahrávky.

Na prvním cvičení jsme se bavili o Turingových strojích. Zavedli jsme hlavně z důvodu přesnějšího měření prostorové složitosti vícepáskové stroje s rozlišenými možnostmi read/write přístupů k páskám. Zavedli jsme pojmy display, akce, krok, konfigurace. Definovali jsme i nedeterministické stroje. Definovali jsem časovou a prostorovou složitost.

Nejprve jsme se zabývali možností redukce počtu pásek (nejtěžší část při tvorbě univerzálního stroje) jak posouváním evidovaných poloh hlav po simulované široké pásce, tak posouváním obsahu pásek s udržováním simulovaných hlav na místě. Druhý postup bylo možno šikovnou organizací prázdných, poloprázdných a plných bloků exponenciálně rostoucí délky zorganizovat tak, že jeden krok byl odsimulován v amortizovaném čase $O(\log s)$. Kvůli různým definicím prostorové složitosti jsme pak probrali větu o lineární kompresi, následně i větu o lineárním zrychlení (větší abeceda, taneček na získání potřebných informací na provedení r kroků na 3, pozor na vstupní a výstupní pásky, nutná duplikace vstupní pásky vede ke zdržení $(1+\varepsilon)n$).

Také jsme odhadli počty možných konfigurací stroje s omezenou prostorovou složitostí pro pevný vstup (stroje bez výstupních pásek).

Následně jsme zmínili problém jednostranně nekonečné pásky. Na posledním cvičeních jsme se zabývali problémem děrné pásky, resp. situací, kdy na pásku můžeme zapisovat nejvýše jednou. Na všech verzích cvičení jsem zmínil problém líného hardvéráře (kdy jednotlivé kroky mohou ze změny stavu, posunu a přepsání pásky provádět nejýš 2 a později nejvýš jednu podakci), ale nebyl čas se mu věnovat.

Cvičení 2

Nejprve jsme se věnovali určení velikostí množin abeceda, slovo, jazyk. Abeceda je konečná, množina slov je spočetná (ukázali jsme jak očíslovat slova nad abecedou velikosti 2, a obdobně pro jiné velikosti). Ukázali jsme, že množina jazyků (nad danou abecedou) je nespočetná (připomněli jsme si Cantorovu diagonalizaci). Pak jsme si ukázali, že množina Turingových strojů je spočetná (každému stroji jsme přiřadili přirozené číslo tak, že z čísla bylo možno stroj rekonstruovat, takže šlo o zobrazení prosté) ve skutečnosti bylo přiřazení takové, že pro každý stroj existuje spočetně mnoho čísel jejichž dekódováním dostaneme stroj který bude pracovat zcela stejně jako původní stroj. Některým číslům neodpovídají funkční stroje. Každé takovéto konstrukci říkáme Goedelovo číslování strojů. Jazyk $i$-tého stroje běžne značíme $L_i$. Následně jsme Goedelovo číslování strojů použili v diagonalizaci prokazující nespočetnost množiny jazyků, abychom definovali jazyk $K=\{w_i\mid w_i\not\in L_i\}$, který není přijímán žádným strojem (není rekurzivně spočetný). Definovali jsme bijekci mezi čísly a slovy nad dvouprvkovou abecedou, definovali jsme bijekci (několik možností) mezi uspořádanými dvojicemi čísel a čísly.

Pak jsme se zabývali vzájemným vztahem Turingových strojů a RAM. U RAM jsme museli stanovit nekonstantní čas pro jednotlivé operace, abychom mohli RAM simulovat na TS s polynomiálním zpomalením. Použili jsme již druhou „datovou strukturu“ na Turingově stroji.

Dále jsme si pro účely cvičení definovali bylo „disjunktní sjednocení“ $\oplus$. Dále jsme pracovali s pojmy $\leq_m$ a $\leq_T$ převeditelnosti. Ukázali jsme si $A\leq_m A\oplus B$ i to, že z $A\leq_m C$ a $B\leq_m C$ plyne $A\oplus B\leq C$, taky jsme zjistili co plyne z předpokladu $A\leq_m \overline{A}$ pro rekurzivně spočetný jazyk $A$ a jeho doplněk $\overline{A}$ o rozhodnutelnosti $A$ (je přijímán strojem, který se vždy zastaví). To co popisuji se stalo na nahrávaném cvičení, což se téměř podařilo i na prvním cvičení, zatímco na druhém cvičení jsme v podstatě skončili za RAM (na kterém jsme se předtím docela zasekli).

Cvičení 3

Hmm, nahrávka je bez zvuku, ač jsem mikrofon před začátkem nahrávání testoval:(. Navíc jsem si špatně označil jaká část tabule je nahrávaná, takže se důkaz Savičovy věty ocitl na nahrávce jen velice okrajově.

Nejprve jsme se věnovali vyčíslitelnosti, udělali jsme převod $L_u=\{\langle x,y\rangle\mid y\in L_x\}$ na $\hbox{Inf}=\{m\mid |L_m|=\infty\}$ a $J=L_u \oplus \overline L_u$ na $EQ=\{\langle m,n\rangle \mid L_m=L_n\}$.

Následně jsme se věnovali složitosti. Začali jsme triviálními inkluzemi, kde k důkazu inkluze stačí použít tentýž stroj. Pokračovali jsme metavětami o simulacích nedeterministických výpočtů. Buď jsme si pomohli posloupností dvojic display, akce, pak zjišťováním dosažitelností vrcholů v grafu konfigurací. Prohledávání grafu jsme dělali nejprve co nejrychleji, ale potřebovali jsme exponenciální čas vůči prostoru původního stroje (minimálně však polynomiální vůči velikosti vstupu.) Pak jsme (na dvou cvičeních) řešili deterministicky prostorově efektivní prohledávání grafu (kvadratický prostor vůči původnímu prostoru, přinejmeněím však kvadrát velikosti vstupu. Savičova (Савич) věta.) Na třetím cvičení jsme ještě ukázali, nedeterministicky prostorově efektivní prohledávání grafu, kde výpočet výsledněho stroje vždy buď "zfailuje" nebo vydá správnou odpověď. Vždy aspoň jedna větev výpočtu doběhne. Stačí nám k tomu stejně velký prostor (můžeme tak ve stejném prostoru negovat náležení do jazyka).

Naznačil jsem, že se nám bude pro důkazy hodit konstruovatelnost funkcí. Příští hodinu se konstruovatelnosti budeme věnovat víc.

Cvičení 4

Na první verzi cvičení jsme nejprve dokončili použití metavěty o simulaci nedeterministického stroje s prostorovým omezením.

Věnovali jsme se větám o hierarchii, tedy pro "nárokově omezené třídy složitosti" $Narok(f)$, pro jaké funkce $f,f'$ existuje jazyk v $Narok(f')\setminus Narok(f)$. Ukázali jsme že pro DTime, DSpace a NSpace jazyk $$L=\{1^k0x|{\rm stroj\ }x{\rm\ nepřijímá\ }1^k0x{\rm\ s\ nároky\ }f(|1^k0x|){\rm\ a\ univerzální\ stroj\ to\ s nároky\ }$f'(|1^k0x|)${\rm\ dokáže\ zjistit.}\}$$ patřil do příslušného rozdílu. Podmínkou bylo, aby $f'(|1^k0x|)$ nebylo v $O($ nároků potřebných univerzálním strojem pro simulaci stroje pracujícího s nároky $f(|1^k0x|)$ $)$. ($O$ potřebujeme kvůli tomu, že simulovaný stroj může mít libovolně velkou abecedu, počet pásek apod.) Navíc potřebujeme, aby $f$ a $f'$ byly kostruovatelné a aby bylo možno skládat "triviální" transformace. Skládání triviálních transformací vynucuje $\ge\log n$ v případě prostorových složitostí a $\ge (1+\varepsilon)n$ v případě časové složitosti. V případě deterministické časové složitosti potřebuje univerzální stroj čas $t(n)\log t(n)$ k simulaci, v případě prostorových nároků nám (asymptoticky) stačí stejně velký prostor (a to i v případě nedeterministické negace). Podmínka na univerzální stroj společně se skládáním transformací zajišťují, že $L$ patří do $Narok(f')$, diagonalizačí argument po nafouknutí do velikosti, kdy univerzální stroj dokončí simulaci garantuje, že $L$ nepatří do $Narok(f)$.

Zbylé probírané věty byla zapomněnka.

Naznačil jsem existenci Žákovy věty, která řeší nedeteministickou časovou hierarchii. Zjistil jsem, ale, že se dá na internetu špatně dohledat, tak sem radši napíšu i důkaz. Předpokladem je, aby $f$ a $f'$ byly časově kostruovatelné a pro libovolnou konstantu $c$ existovalo $n_0$, že $\forall n>n_0{\rm\ je\ }f'(n)>cf(n+1)$. Důkaz používá plíživou diagonalizaci jazyka $$L=\eqalign{\{0^t1^k0x|{\rm\ deterministicky\ dopočítáme\ v\ čase\ }t{\rm,\ že\ }1^k0x\not\in L_x{\rm\ nebo\ na\ to\ }t{\rm\ nestačí\ a}\hfil\cr {\rm nedeterministicky\ v\ čase\ }f'(|0^t1^k0x|){\rm\ odsimulujeme\ }0^{t+1}1^k0x\in L_x.\}\cr}$$ (Na simulaci používáme příslušný fixní univerzální stroj, výpočty běží paralelně, k tomu potřebujeme skládání transformací (inicializace), tedy $f'\ge (1+\varepsilon)n$.) Pokud by $y$ v čase $f$ přijímal $L$. Nechť $c$ je konstanta kolikrát víc času potřebuje univerzální stroj k simulaci stroje $y$. Dofoukneme $y$ na $1^k0y$ tak aby $|1^k0y|>n_0$ (z předpokladu). Pak má univerzální stroj vždy dost času aby odsimuloval výpočet v čase $f$ pro o jedna delší vstup. Nechť $T$ je čas, který poprvé stačí na deterministickou simulaci $1^k0y\in L_y$, pak $$1^k0y\in L\Leftrightarrow 01^k0y\in L_y\Leftrightarrow 01^k0y\in L\Leftrightarrow 0^21^k0y\in L_y\Leftrightarrow 0^21^k0y\in L \cdots 0^T1^k0y\in L_y\Leftrightarrow 0^T1^k0y\in L\not\Leftrightarrow 1^k0y\in L_y.$$ Za zmínku stojí si uvědomit, jak může nedeterministický stroj efektivně odsimulovat deterministický výpočet pracující v čase $t$. Budeme jej simulovat stejně, jako kdyby byl nedeterministický, díky tomu, že dokážeme zkontrolovat pásky nezávisle nepotřebujeme řešit jejich synchronizaci a stačí nám čas $O(t)$ a s použitím lineárního zrychlení $t$ (víme, že $t≥(1+\varepsilon)n$). Deterministický stroj, který simulujeme kontroluje všechny možné posloupnosti (displej, akce) odpovídající výpočtům v čase $f(|1^k0x|)$, takže $t\in 2^{cf(|1^k0x|)}$, ale velikost $t$ není podstatná.

Následně jsem dokázal Borodinoovu větu, která říká, že pro předepsané $f,g$ totálně vyčíslitelné funkce ($g(n)>n$) existuje totálně vyčíslitelná funkce $s\ge f$ (předvádíme konstrukci) taková, že $DSpace(s(n))=Dspace(g(s(n)))$. Pro $f(n)=\log n$ a např. $g=2^n$ dostáváme, že $s$ není prostorově konstruovatelná funkce (jinak bychom měli spor s větou o hierarchii).

Na druhém a třetím cvičení jsem ještě stihnul naznačit Blumovu větu, která říká, že hon za nejefektivnějším algoritmem pro daný problém nemusí vždy dávat smysl. Zvětšováním kódu může stále docházet k snižování nároků na výpočet. Konkrétně pro danou totalní rekurzivní funkci $r$ (můžeme předpokládat že je neklesající a aspoň $n^2$) existuje rekurzivní jazyk $L$ takový, že $L_i=L\Rightarrow\exists\,j\ L_j=L{\rm\ a\ }\forall^* n\ r(s_j(n))\le s_i(n)$. Při důkazu je nejprve definováno $h(1)=2{\rm\ a\ }h(n)=r(h(n-1))$, pak je definován jazyk $L\subseteq 0^*$ splňující následující dvě podmínky: $$1) L_k=L \Rightarrow \forall^* n\ s_k(n)\ge h(n-k)$$ $$2) \forall k\ \exists j\ L_j=L \wedge s_j(n)\le h(n-k)$$ Jejich složením při dosazení $i$ resp $i+1$ za $k$ dostáváme požadovaný výsledek. K zajištění podmínek pro definici toho, zda $0^n$ patří do $L$ vezmeme první dosud nezakázaný stroj $i\le n$, jehož nároky $s_i(n)<h(n-i)$ a označíme $\sigma(n)=i$ (nemusí být definováno) ($i$ nezakázaný znamená $\forall m<n\ i\not=\sigma(m)$). Stroj $\sigma(n)$ zakážeme tím, že diagonalizačně definujeme $0^n\in L\Leftrightarrow 0^n\not\in L_{\sigma(n)}$. Při nedefinovaném $\sigma(n)$ definujeme $0^n\not\in L$. Pokud zakřížkueme body $(j,n)$, kde $\sigma(n)=j$, tak na každém řádku je nejvýš jeden křížek a na řádcích až do $k$ je nějaký křížek nejvíc vpravo. Jeho sloupec nazvěme $n_0$. V překladu $\exists n_0>k\ \forall j<k\ \sigma(n)=j\Rightarrow n\le n_0$. Protože stroj $L_k=L$, nemohl být $k$ zakázán a pro $n>n_0$ již k zrušení menšího stroje nedojde, tak $s_k(n)<h(n-k)$ by znamenalo zakázání stroje $k$, takže podmínka 1) platí. Druhá podmínka je techničtější. Na rozdíl od Borodinovy věty potřeba odhadnout zpoždění při sumulaci stroje $i$ na základě $i$. Co potřebuje stroj $j$ znát, k rozhodnutí, zda $0^n\in L$? Pokud existuje $\sigma(n)$ je potřeba zjistit, zda $0^n\in L_{\sigma(n)}$. K zjištění, že $i=\sigma(n)$ potřebujeme zjistit, že $s_i(n)<h(n-i)$, že $i$ nebyl zrušen kratšími slovy a že žádné menší $i'$ nemá takovou vlastnost. Algoritmu může pracovat tak, že pro $m$ od nejmenších najde $\sigma(m)$ a zapamatuje si jej (pokud existuje) pro další použití. Pro zjištění, zda $s_i(n)<h(n-i)$ potřebujeme prostor $n+(h(n-i)+\log n+1)\lceil \log i\rceil$, ale náš stroj smí použít prostor nejvýš $h(n-k)$. Náš stroj tedy nemůže simulovat stroj $i$ pro $i\le k$. Řešením je obdobně jako u první podmínky najít $n_0$ a konečně mnoho případů pro $n\le n_0$ zaznamenat do konstant kódu (společně se seznamem zrušených strojů pro $n\le n_0$, navíc víme, že pro $n>n_0$ nebude zrušen stroj $i\le k$, takže si nemusíme pamatovat zrušené stroje s indexy mešími než $k$). Ještě je potřeba zkontrolovat kolik prostoru potřebujeme pro simulaci pro $n>n_0$ včetně délky seznamu zrušených strojů od $n_0$ dál a tím splnitelnost podmínky 2 ověříme.

Cvičení 5

Řěsili jsme NP-úplnost a převoditelnost mezi problémy. Hlavně jsem se zaměřoval na techniku ukázání možnosti zakódovat v našem problému proměnnou a její negaci a možnosti nezávisle na sobě vytvořit klauzuli, kterou je možno splnit právě pokud je některý její literál pravdivý. Ukázali jsme si tuto techniku na problému barvení grafu 3mi barvami, na hledání nezávislé množiny dané velikosti či na hledání Hamiltonovské kružnice v orientovaném rovinném bipartitním grafu s (in,out) stupni vrcholů (2,1) v jedné a (1,2) v druhé partitě (Plesník). Kromě toho jsme na různých verzích cvičení stihli různé odbočky. (1 in 3 Sat), součet podmnožiny, různé verze kachlíčkování, včetně plumber s kachlíky 0,1,I,L, had.