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

Last Modified: 3.12.2024

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

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 cvičení a termín na jejich odevzdání je u úkolu explicitně uveden (vždy 10:40). (Jedná se o počátek cvičení 14 dní po počátku třetí verze cvičení). 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

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.

Kvůli různým definicím prostorové složitosti jsme 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$). Dále 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)$.

Následně jsme zmínili problém jednostranně nekonečné pásky. Na všech cvičeních jsme se zabývali problémem děrné pásky, tedy 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.

Nedostali jsme se k odhadům počtu možných konfigurací stroje s omezenou prostorovou složitostí pro pevný vstup (stroje bez výstupních pásek). Nezbyde nám než se k tomu vrátit až se budeme zabývat složitostí.

Cvičení 2

Na první verzi druhého cvičení jsme probrali spoustu věcí, ale nezmínili, jak kódovat uspořádané dvojice. Jedna z variant byla zmíněna na přednášce. Bavili jsme se o vztahu RAM a TS (RAM musíme zvolit vhodnou cenu operací, aby byly polynomiálně ekvivalentní). Následně jsme se bavili o abecedách, slovech a jazycích, jejich počtech, definovali základní pojmy a nepatrně si hráli s převoditelností.

Cvičení 3

Po krátkém zmínění na problému $EQ={\langle M,N\rangle\mid L_M=L_N}$ jsme opustili vyčíslitelnost a věnovali se složitosti.

Po zmínění triviálních vztahů mezi třídami $(N)Time(f(n))$ a $(N)Space(f(n))$ jsme popsali metavěty o simulaci časově resp. prostorově omezených výpočtů (práce s posloupností display/akce, resp. prohledávání grafu potenciálně dosažitelných konfiguací). Probémy konstruovatelnosti byly zmíněny jen orientačně. Dostali jsme tak simulace dokazující $NTime(f(n))\subseteq Space(f(n))$, ale i existenci univerzálního nedeterministického stroje pro simulaci výpočtů v čase $t(n)$ v čase $t(n)$ (pro $t(n)>(1+\varepsilon)n$). Taky jsme dostali $NSpace(f(n))\subseteq \bigcup_c Time(2^{c(f(n)+\log n)})$, $NSpace(f(n))\subseteq Space((f(n)+\log n)^2)$, ale i to, že ke stroji garantujícímu že $L\in NSpace(f(n))$ (přijímající daný jazyk s danými prostředky) jsme schopni algoritmicky vytvořit stroj garantující $\overline{L}\in NSpace(f(n))$.

Cvičení 4

Nejprve jsme se trochu zabývali nutností předpokladu konstruovatelnosti a pro simulace kdy simulující stroj byl prostorově omezen jsme mohli dostupné prostředky simulovaného stroje postupně zvětšovat čímž jsme se potřebě konstruovatelnosti mohli vyhnout. Pro nedeterministický univerzální stroj pro časově omezené výpočty bychom dokázali udělat stroj, který přijímá v (až na konstantu závislou na simulovaném stroji) stejném čase, ale s nekonečnou větví výpočtu.

Následně jsme dokázali věty o hierarchiích pro (N)Space a Time, a naznačili Žákovu větu o hierarchii pro NTime (kde místo předpokladu $f_2(n)\not \in O(u(f_1))$, kde $u$ je funkce zachycující funkcionální zpomalení univerzální simulací ($u(n)=n$ resp. $u(n)=n\log n$ pro space resp. time) je předpoklad $f_1(n+1)\in o(f_2(n))$. Obě věty vyžadují aby $f_2$ byla příslušně konstruovatelná. U první věty navíc potřebujeme, aby $f_1(n)$ bylo možno spočítat s prostředky $f_2(n)$. Žákova věta s plíživým padding byla podána jen jako zapomněnka.

Následně jsme se věnovali v rámci zapomněnky ještě Borodinově větě o mezerách, která naznačila, proč je konstruovatelnost potřeba. Blumovu větu o zrychlení (kompresi) jsme vůbec nedokazovali, nicméně byla zmíněna. K trikům s paddingem umožňujícím dokazovat některé hierarchické vztahy pro Time, když je $u(f_1)$ moc velké jsme se nedostali.