Vladan Majerech - NTIN090 Základy složitosti a vyčíslitelnosti
Last Modified: 25.1.2020
Index
zápočtové příklady, odkazy, cvičení 1, cvičení 2, cvičení 3, cvičení 4, cvičení 5, cvičení 6.
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). Cvičím v úterý liché i sudé týdny. Úkoly jsou zadávány brzy po prvním úterním cvičení a termín na jejich odevzdání je do počátku úterního cvičení 14 dní po druhém cvičení. Za domácí úkoly vypracované v termínu je možno získat plný počet uvedených bodů. 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ů.
Zápočtové příklady
| kód | Body | Termín odevzdání | Zadání | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| směr | 1 | 22.10.2019 9:00 | Ukažte, jak lze libovolný jednopáskový Turingův stroj $M$ převést na stroj $M'$, který se od normálního jednopáskového Turingova stroje liší tím, že páska je jen jednostranně nekonečná. | |||||||||
| reset | 2 | 22.10.2019 9:00 | Ukažte, jak lze libovolný jednopáskový Turingův stroj $M$ převést na Resetovací (jednopáskový) stroj $M'$, který se od Turingova stroje liší tím, že přechodová funkce neumožňuje pohyb doleva o jedno políčko, ale pouze pohyb na začátek (jednostranně nekonečné) pásky. | |||||||||
| $\exists\forall$ | 2 | 5.11.2019 9:00 | Ukažte, že jazyk $L$ je rozhodnutelný, právě když existují rozhodnutelné jazyky $A$ a $B$, pro které platí, že $L=\{x\;|\;(\exists y)[\langle x, y\rangle\in A]\}= \{x\;|\;(\forall y)[\langle x, y\rangle\in B]\}$ | |||||||||
| prime | 1 | 5.11.2019 9:00 | Popište algoritmus (pro Turingův stroj), který ignoruje svůj vstup a na výstup vypisuje postupně všechna prvočísla v rostoucím pořadí. | |||||||||
| reg | 1 | 19.11.2019 9:00 | Nechť $B$ je jazyk přijímaný konečným automatem a nechť $A$ je jazyk pro nějž $A\le_m B$. Je $A$ regulární? Proč? | |||||||||
| size | 2 | 19.11.2019 9:00 | Je jazyk $\hbox{Size}=\{\langle M,k\rangle\mid |L(M)|\ge k\}$ rozhodnutelný? Je částečně rozhodnutelný? | |||||||||
| EQ | 3 | 10.12.2019 9:00 | Je jazyk $\hbox{EQ}=\{\langle M,N\rangle\mid L(M)=L(N)\}$ rozhodnutelný? Je částečně rozhodnutelný? Je jeho doplněk částečně rozhodnutlný? | |||||||||
| inkluze | 3 | 7.1.2020 9:00 |
O kterých inkluzích mezi následujícími dvojicemi tříd jste schopni dokázat,
že platí a o kterých, že neplatí.
Za každý dokázaný vztah je jeden bod
(do požadovaného počtu bodů započítáno za 3).
|
V následující tabulce je uveden aktuální stav získaných bodů jednotlivých studentů.
| Id studenta | celkem | detail |
|---|---|---|
| Q | 4 | směr(1), reset(2), prime(1), $\exists\forall$(0), reg(0), size(0) |
| T | 6 | směr(1), reset(2), prime(1), $\exists\forall$(1), reg(1), size(0) |
| e | 3 | směr(1), reset(2) |
| f | 5.8 | směr(1), reset(2), prime(1), reg(1), size(0.8) |
| i | 3 | směr(1), reset(2) |
| n | 5 | směr(1), reset(2), $\exists\forall$(2), EQ(0) |
| Id studenta | celkem | detail |
|---|---|---|
| A | 10 | směr(1), reset(2), prime(1), $\exists\forall$(1), reg(1), size(2), EQ(2) |
| B | 10 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(2), EQ(1) |
| C | 11 | směr(1), reset(2), prime(1), $\exists\forall$(1), reg(1), size(2), EQ(3) |
| D | 15 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(2), EQ(3), inkluze(3) |
| E | 10 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(2), EQ(1) |
| F | 12 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(2), EQ(3) |
| G | 12 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(2), EQ(3) |
| H | 11 | směr(1), reset(2), prime(1), $\exists\forall$(1), reg(1), size(0), EQ(2+1/2), inkluze(5/2) |
| I | 10 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), EQ(3) |
| J | 10 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), EQ(3) |
| K | 12 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(2), EQ(3) |
| L | 11 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(1), EQ(3) |
| M | 11 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(1), EQ(3) |
| N | 11 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(1), EQ(3) |
| O | 11 | směr(1), reset(2), prime(1), $\exists\forall$(1), reg(1), size(2), EQ(3) |
| P | 12 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(0), EQ(2), inkluze(3) |
| R | 10 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(0), EQ(3) |
| S | 11 | směr(1), reset(2), prime(1), reg(1), size(0), EQ(3), inkluze(3) |
| U | 10 | směr(1), reset(2), reg(1), size(2), EQ(3), inkluze(1) |
| V | 11 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(1), EQ(3) |
| W | 12 | směr(1), reset(2/2), prime(1), $\exists\forall$(0), reg(1), size(2), EQ(3), inkluze(3) |
| X | 11 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(2), EQ(2) |
| Y | 11 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(1), EQ(3) |
| Z | 14 | směr(1), reset(0), prime(1), $\exists\forall$(1), reg(1), size(2), EQ(2), inkluze(6) |
| a | 10 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(0), EQ(3) |
| b | 10 | směr(1), reset(2), prime(1), reg(1), size(2), EQ(3) |
| c | 10 | směr(1), reset(2), prime(1), reg(1), size(2), EQ(3) |
| d | 10 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), EQ(3) |
| g | 12 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(2), EQ(3) |
| h | 10 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), EQ(3) |
| j | 11 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(1), EQ(3) |
| k | 11 | směr(1), reset(2/2), prime(1), reg(1), EQ(1), inkluze(6) |
| l | 12 | směr(1), reset(2), prime(1), $\exists\forall$(2), reg(1), size(2), EQ(3) |
| m | 10 | směr(1), $\exists\forall$(2), EQ(3), inkluze(3), size(2/2) |
| o | 10.5 | směr(1), reset(0), prime(1), $\exists\forall$(2), reg(1), size(1), EQ(3/2), inkluze(6/2) |
| ? | 12 | směr(1), reset(1), prime(1), $\exists\forall$(2), size(1), EQ(3), inkluze(3) |
Odkazy na obdobné stránky
Cvičení Petra Kučery, Petra Gregora a moje loňská.
Cvičení 1
Na cvičení jsme pracovali s Turingovými stroji. Použili jsme pojmy display, krok(akce), stav, abeceda, přechodová funkce (měli jsme použít i pojem konfigurace). Hovořili jsme o vícepáskových strojích, kde mohou být pásky rozdělené na read-only, read-write and write-only, a je možno pak lépe hovořit o skutečných (sublineárních) prostorových nárocích algoritmu. Naznačili jsme existenci deterministické i nedeterministické varianty, diskutovali jsme počáteční (a měli jsme diskutovat i koncovou konfiguraci stroje).
Taky jsme naznačili existenci RAM a toho, jak jej polynomiálně odsimulovat na TS (pokud do času instrukce počítáme $\log$ maximálního operandu)
Zabývali jsme se problémem redukce počtu pásek, ale stačilo nám řešení s časovou složitostí redukce se zpomalením $O(n)$ (šlo by i zpomalení jen $O(\log n)$ - bylo na druhém cvičení).
Pak jsme řešili úlohu „líných hardwareářů“, jak transformovat přechodovou funkci jednopáskového stroje tak, aby nikdy neprováděl současně 3 z akcí změň písmeno na pásce, změň stav, změň polohu. Pak jsme si pohráli i s tím, aby nikdy neprováděl současně 2 z těchto akcí.
Pak jsme se (na prvním cvičení) věnovali simulaci HW s děrnou páskou, tedy úloze, kdy je na políčko pásky možno napsat netriviální symbol jen jednou. (V první variantě bylo možno symbol následně zakaňkovat, v druhé variantě jsme již ani nemohli dělat kaňky).
Cvičení 2
Nejprve jsme dohnali to, co jsme udělali na předchozím cvičení druhé skupiny. Pak jsme se věnovali přijímání $L^*$, kde $L$ byl rekurzivně spočetný jazyk.
Pak jsme definovali disjunktní sjednocení a ukázali si jeho možné implementace. Nakonec jsme řešili jaký je vztah disjunktního sjednocení a převoditelnosti.
Cvičení 3
Na cvičení jsme se zabývali převážně převeditelností. Dále jsme dokazovali $A\le_m \overline{A}$ pro částečně rozhodnutelné $A$ vynucuje rozhodnutelnost $A$. Pak jsme definovali $L_u=\{\langle x,y\rangle\mid M_x(y)\downarrow\hbox{ANO}\}$. Kvůli tomu jsme řešili možnosti kódování dvojic, a to především ty, které nepotřebují rozšiřovat abecedu. V případě unární abecedy nás z hlediska složitosti exponenciální nárůst velikosti vstupu kvůli kódování nepotěšil.
Pak jsme se zabývali protipříkladem proti tomu, že spočetná množina může obsahovat nespočetně mnoho hodnot. V případě Turingových strojů jsme tak ukázali existenci jazyka, který není ani částečně rozhodnutelný. Na rozdíl od intervalu reálných čísel jsme nemuseli řešit kompilace s dvojznačností.
Dále jsme se zabývali jazykem $J=L_u\oplus \overline{L_u}$. Argument existence jazyka, který není ani částečně rozhodnutelný jsme využili k důkazu toho, že ani $J$, ani $\overline{J}$ nejsou částečně rozhodnutelné. Využili jsme toho, že $L_u$ je „částečně rozhodnutelně úplný“ a dostali bychom spor v tom, že by všechny částečně rozhodnutelné jazyky byly rozhodnutelné. Během hodiny jsme použili jazyky $\{x\mid M_x(x)\uparrow\}$, $\{x\mid M_x(x)\downarrow\}$.
Na druhém cvičení jsme si navíc chvilku povídali o Riceho větě a o postově korespondenčním problému.
Cvičení 4
Na cvičení jsme se zabývali třídami složitosti $(N)Time(f(n))$ a $(N)Space(f(n))$. Ukázali jsme si základní inkluze nevyžadující simulaci „jinak“. Pak jsem vyslovil metavěty o simulacích (prostorově omezené výpočty simulujeme procházením grafu konfigurací, časové procházením stromu výpočtu, případně posloupností dvojic(display,akce)).
Odhadli jsme počet konfigurací prostorově omezeného výpočtu a použili jsme metavěty k vnoření $NSpace(f(n))\subseteq \bigcup_c Time(2^{c(f(n)+\log n)})$, $NTime(f(n))\subseteq Space(f(n))$ a $NSpace(f(n))\subseteq Space((f(n)+\log(n))^2)$. Ukázali jsme, že nepotřebujeme předem znát $f(n)$, abychom vnoření provedli (iterativním zvětšováním nároků a simulací výpočtů omezených daným nárokem). Pokud simulovanému výpočtu daný nárok stačil, simulující stroj simulaci s odpovídajícím nárokem zvládl. Pokud simulovanému výpočtu nárok nestačil, nevadí, že simulaci nezvládneme. Potíž bude se stroji, které mají pro přijetí některých slov nárok nepatrně větší než $f(n)$. Je-li $L(f(n))$ jazyk slov přijatých takovýmto strojem s omezením $f(n)$, je takovýto stroj garantem $L(f(n))\in Omezeni(f(n))$? U konstruovatelných funkcí takový problém s definicí není, protože jsme schopni vytvořit stroj, který přijímá právě $L(f(n))$ a vždy to zvládne s omezením $f(n)$.
Při té příležitosti jsme probrali lineární kompresi a lineární zrychlení (s bariérou $n(1+\varepsilon)$).
Ke konci hodiny jsme ještě použili metavěty na konstrukci univerzálního stroje pro $NTime(f)$, kterému stačí $O(f)$ času (nedocházi k asymptotickému zpomalení kvůli simulaci více pásek, než má univerzální stroj). Funkci $f$ jsme ale potřebovali znát předem (a musela být konstruovatelná). Na závěr jsem naznačil použití metavěty na konstrukci univerzálního stroje pro $NSpace(f)$, který v prostoru $O(f)$ dokáže rozhodnout, zda simulovaný stroj přijal či ne (dává dva možné garantované výstupy, případně větev výpočtu vydá fail). Vždy existuje větev výpočtu která skončí jinak než fail a vydá správnou odpověď. Opět jsme potřebovali $f$ předem znát (a musela být konstruovatelná) protože se odpověďi liší v závislosti na $f$. Tato konstrukce garantuje, že $NSpace(f)$ je uzavřená na doplňky jazyků.
K větám o hierarchii jsme se nedostali.
Na druhém cvičení jsme udělali i tu uzavřenost $NSpace(f)$ na doplňky, navíc jsme stihli naznačit, jak bude vypadat jazyk vklíněný mezi třídy složitostí lišící se použitou funkcí. Zbývá si rozmyslet, za jakých předpokladů skutečně jazyk do jedné třídy patřit bude a do druhé ne.
Cvičení 5
Na prvním cvičení jsme dodělali simulaci nedeterministického prostorově omezeného výpočtu stejně omezeným výpočtem, který ale má vlastnost, že pro každé slovo některá větev výpočtu správně odpoví, zda patří do jazyka a žádná neodpoví špatně.
Pak jsme se věnovali větám o hierarchii pro $Time$, $Space$ a $NSpace$. ($L=\{1^k0x\mid$ stroj $x$ daného typu nepřijme s omezením $f(|1^k0x|)$ vstup $1^k0x$ a daný univerzální stroj daného typu to dokáže zjistit s omezením $f'(|1^k0x|)\}$ patří do třídy strojů daného typu s omezením $f'$ ale ne s omezením $f$.) Ke konci hodiny jsme probrali i prodlužovací lemma a použili jej k důkazu $Time(2^n)\not=Time(n2^n)$.
Na druhém cvičení jsme si povídali i o NP-úplnosti. Ukázali jsme si NP-úplnost SAT ze znalosti NP-úplnosti KACHL, ukázali jsme si NP-úplnost „1 in 3 SAT“, pak jsem ukazoval jak modelovat literály a klausule pomocí 3 color, a nakonec pomocí Hamiltonovské kružnice s hodně malými stupni vrcholů (Plesník).
Cvičení 6
Na posledním cvičení jsme se věnovali NP-úplnosti a převodům (převážně ve stylu „jsme schopni deklarovat booleovské proměnné a jejich negace, jsme schopni vytvořit nezávislé klauzule“). Tímto stylem jsme probrali jak 3-barevnost, tak Plesníkův důkaz npúplnosti hledání HC v grafu s malými stupni, tak NP-úplnost NM dané velikosti. Přitom jsme prošli 1 in 3 SAT i rozhodnutí, kterou cestou se had má vydat. Nakonec v rychlosti zaznělo i kachlíčkování se seznamem kachlíků místo katalogu.