Vladan Majerech - NTIN090 Základy složitosti a vyčíslitelnosti
Last Modified: 30.1.2019
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, cvičení 7.
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 pondělí liché i sudé týdny. Úkoly jsou zadávány brzy po prvním pondělním cvičení a termín na jejich odevzdání je do počátku pondělní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ů.
Pokud někomu chybí připsané body ke dni 24.11, tak se mi ozvěte.
Zápočtové příklady
| kód | Body | Termín odevzdání | Zadání | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| reset | 1 | 22.10.2018 10:40 | 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. | |||||||||
| $2\times$piš | 1 | 22.10.2018 10:40 | Ukažte, jak lze libovolný jednopáskový Turingův stroj $M$ převést na (jednopáskový) Turingův stroj $M'$, který má omezení, že každé políčko pásky je možno přepsat pouze dvakrát (zápisy neměnící obsah se nepočítají). | |||||||||
| $1\times$piš | 1 | 22.10.2018 10:40 | Ukažte, jak lze libovolný jednopáskový Turingův stroj $M$ převést na (jednopáskový) Turingův stroj $M'$, který má omezení, že každé políčko pásky je možno přepsat pouze jednou (zápisy neměnící obsah se nepočítají). | |||||||||
| $\exists\forall$ | 2 | 5.11.2018 10:40 | 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.2018 10:40 | 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.2018 10:40 | 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.2018 10:40 | Je jazyk $\hbox{Size}=\{\langle M,k\rangle\mid |L(M)|\ge k\}$ rozhodnutelný? Je částečně rozhodnutelný? | |||||||||
| EQ | 3 | 3.12.2018 10:40 | 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 | 17.12.2018 10:40 |
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).
| |||||||||
| HC | 3 | 14.1.2019 10:40 | Dokažte, že zjištění zda v grafu existuje Hamiltonovská cesta je NP-těžké, jak ve variantě neurčených koncových bodů cesty, tak i v případě, kdy jsou jeden či oba koncové vrcholy určeny (jak pro orientované, tak pro neorientované grafy). |
V následující tabulce je uveden aktuální stav získaných bodů jednotlivých studentů.
| Id studenta | celkem | detail |
|---|---|---|
| A | 12 | reset(1), $\times$piš(2), $\forall\exists(2)$, prime(1), reg(1), size(2), EQ(3) |
| B | 10.5 | reset(1), 2$\times$piš(1), 1$\times$piš(1), $\forall\exists(2)$, prime(1), reg(1), size(1), inkluze(2.5) |
| C | 12 | reset(1), 2$\times$piš(1), 1$\times$piš(1), $\forall\exists(2)$, prime(1), reg(1), size(2), EQ(3) |
| D | 4 | reset(1), $\times$piš(2), prime(1) |
| E | 12.5 | reset(1), 2$\times$piš(1), 1$\times$piš(1), $\forall\exists(1)$, prime(1), reg(0), size(.5), EQ(3), inkluze(4) |
| F | 12 | reset(1), 2$\times$piš(1), 1$\times$piš(1), $\forall\exists(2)$, prime(1), reg(1), size(2), EQ(3) |
| G | 10.5 | reset(1), 2$\times$piš(1), 1$\times$piš(1), $\forall\exists(0)$, prime(1), reg(1), size(0), EQ(3), inkluze(2.5) |
| H | 10.5 | reset(1), $\times$piš(2), prime(1),$\forall\exists(1.5)$, reg(1), size(2), EQ(2) |
| I | 11 | reset(1), 2$\times$piš(1), 1$\times$piš(1), $\forall\exists(2)$, prime(1), reg(1), size(2), EQ(2) |
| J | 10 | reset(1), $\times$piš(2), prime(0), reg(1), size(2), EQ(3), inkluze(1) |
| K | 10 | reset(1), 2$\times$piš(1), 1$\times$piš(1), $\forall\exists(2)$, prime(1), reg(1), size(2), EQ(1) |
| L | 11 | reset(1), 2$\times$piš(1), 1$\times$piš(1), $\forall\exists(2)$, prime(1), reg(1), size(1), EQ(3) |
| M | 3.7 | reset(1), 2$\times$piš(1), 1$\times$piš(1), prime(0), reg(0.7), size(0) |
| N | 11 | reset(1), $\times$piš(2), $\forall\exists(2)$, prime(1), size(2), EQ(3) |
| O | 3 | reset(1), $\times$piš(2) |
| P | 12 | reset(1), 2$\times$piš(1), 1$\times$piš(1), $\forall\exists(2)$, prime(1), reg(1), size(2), EQ(3) |
| Q | 11.5 | reset(1), $\times$piš(2), $\forall\exists(2)$, prime(.5), reg(1), size(2), EQ(3) |
| R | 10 | reset(1), 2$\times$piš(1), 1$\times$piš(1), $\forall\exists(2)$, prime(0), reg(.5), size(.5), EQ(3), inkluze(1) |
| S | 10.5 | reset(.5), 2$\times$piš(1), 1$\times$piš(1), $\forall\exists(1)$, prime(1), reg(1), size(2), EQ(3) |
| T | 10.6 | reset(1), 2$\times$piš(1), 1$\times$piš(1), $\forall\exists(.8)$, prime(.8), reg(0), size(2), EQ(1), inkluze(3) |
| U | 2.7 | reset(.5), 2$\times$piš(1), 1$\times$piš(.5), $\forall\exists(0)$, prime(.7) |
| V | 11 | reset(1), 2$\times$piš(1), 1$\times$piš(1), $\forall\exists(1)$, prime(0), reg(1), size(0), EQ(3), inkluze(3) |
| W | 12 | reset(1), 2$\times$piš(1), 1$\times$piš(1), $\forall\exists(2)$, prime(1), reg(1), size(2), EQ(3) |
| X | 10 | reset(1), $\times$piš(2), $\forall\exists(1)$, prime(1), reg(1), size(1), EQ(3) |
| Y | 11 | reset(1), $\times$piš(2), $\forall\exists(1)$, prime(1), reg(1), size(2), EQ(3) |
| Z | 11 | reset(1), $\times$piš(2), $\forall\exists(2)$, prime(1), reg(1), size(1), EQ(3) |
| a | 7.7 | reset(1), 2$\times$piš(0), 1$\times$piš(1), $\forall\exists(1)$, prime(.7), reg(1), size(1), EQ(1), inkluze(1) |
| b | 2.5 | reset(.5), 2$\times$piš(1), $\forall\exists(1)$, prime(0) |
| c | 11 | reset(1), 2$\times$piš(1), 1$\times$piš(1), $\forall\exists(1)$, prime(1), reg(1), size(2), EQ(3) |
| d | 11.5 | reset(1), $\forall\exists(2)$, prime(1), reg(1), size(1.5), EQ(3), inkluze(2) |
| e | 10 | reset(0), 2$\times$piš(1), 1$\times$piš(.5), $\forall\exists$(1.5), prime(1), reg(1), size(2), EQ(1), inkluze(2) |
| f | 11 | reset(1), $\times$piš(2), $\forall\exists(1)$, prime(1), reg(1), size(2), EQ(3) |
| g | 3.5 | reset(1), 2$\times$piš(1), 1$\times$piš(1), prime(0), reg(.5), size(0), EQ(1) |
| h | 11 | reset(1), 2$\times$piš(1), 1$\times$piš(1), $\forall\exists(1)$, prime(1), reg(1), size(2), EQ(3) |
| i | 12.5 | reset(.5), $\forall\exists(2)$, prime(1), reg(1), size(2), EQ(3), HC(3) |
| j | .8 | $\forall\exists(0)$, prime(.7), reg(0), size(.1), EQ(0) |
| k | 14 | reset(1), $\times$piš(2), $\forall\exists(2)$, prime(1), reg(1), size(1), EQ(3), inkluze(3) |
| m | 1 | $\forall\exists(0)$, prime(1) |
| n | .5 | $\forall\exists(.5)$ |
| o | 6 | reg(1), size(0), EQ(0), inkluze(5) |
Odkazy na obdobné stránky
Cvičení Petra Kučery a Petra Gregora.
Cvičení 1
Na prvním cvičení jsme pracovali s Turingovými stroji. Použili jsme pojmy konfigurace, display, krok(akce), stav, abeceda, přechodová funkce, 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í i koncovou konfiguraci stroje. Pak jsme řešili úlohu, 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í. Dále jsme se zabývali problémem redukce počtu pásek a to i s ohledem na časovou složitost redukce (zvládli jsme zpomalení $O(\log n)$). Na konci hodiny jsme se zabývali redukcí jednopáskového stroje na stroj s jednostranně nekonečnou páskou.
Cvičení 2
Na začátku cvičení jsme si povídali o RAM a jeho vztahu k TS. Zmínil jsem složitostní aspekty RAM (triky s kódováním velké informace do jedné buňky vedoucí k nerealistickým složitostem), a jak se problémům vyhnout (čas operace závisí i na velikosti operandů a výsledku (pro malé hodnoty počítáno konstantou) ... $\lfloor\log M/(1+\log n)\rfloor$). Upozornil jsem na rychlost světla a tímpádem dosažitelnost pouze z kubického množství adres v závislosti na čase (RAM nerealisticky dokáže adresovat až z exponenciálně adres).
Pak jsme si popsali úskalí simulace TS pomocí RAM a opačně RAM pomocí TS. Trik s kešováním použitých buněk paměti pomohl zajistit nejvýš polynomiální zpomalení při druhé simulaci.
Koncem hodiny jsme řešili zřetězení ($L^*$) pro rozhodnutelné a čátečně rozhodnutelné jazyky. Přišli jsme na nutnost simulace paralelně spuštěných výpočtů pro částečně rozhodnutelné jazyky. Trikem bylo iterativní prohlubování počtu simulovaných kroků.
Úplně na konci hodiny 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í. Diagonalizace se nám určitě ještě bude hodit.
Na pozdějším cvičení jsme ještě stihli pár příkladů na převoditelnost. Ukázali jsme, že pro netriviální jazyk $B$ a rekurzivní jazyk $A$ je vždy $A\le_mB$. Definoval jsem (pro účel cvičení) disjunktní sjednocení $A\oplus B=\{a0\mid a\in A\}\cup\{b1\mid b\in B\}$ a ukázali jsme i $A\le_m A\oplus B$ a $(A\le_m C\wedge B\le_m C)\Leftrightarrow (A\oplus B)\le_m C$.
Cvičení 3
Na cvičení jsme se zabývali převeditelností. (Na prvním cviření jsme začali příklady s netriviálním $B$ a s $A\oplus B$) Dále jsme dokazovali $A\le_m \overline{A}$ pro částečně rozhodnutelné $A$ vynucuje rozhodnutelnost $A$. Pak pro $L_u=\{\langle x,y\rangle\mid M_x(y)\downarrow\hbox{ANO}\}$ jsme se zabývali jazykem $J=L_u\oplus \overline{L_u}$ a ukázali jsme že je převeditelný na $\overline{J}$ a že ani $J$, ani $\overline{J}$ nejsou částečně rozhodnutelné.
Mimo jiné jsme se zabývali i tím, jak zařídit alternativní konstrukci disjunktního sjendnocení $A\oplus' B=\{\oplus_1(a)\mid a\in A\}\cup\{\oplus_2(b)\mid b\in B\}$, která by měla stejné vlastnosti ($\oplus_1$ má disjunktní obor hodnot s $\oplus_2$, obě se dají jednoduše počítat i invertovat), ale nerozšiřovala abecedu. (Pro unární abecedu, kde na vstupu jsou kromě souvislého úseku jednoho znaku jen symboly blank si můžeme pomoci transformací délky na $2k$ resp. $2k+1$).
Cvičení 4
Začali jsme převodem $L_u$ na Postův korespondenční problém.
Pak jsme ukázali princip lineárnícho zrychlování i jeho mez na $(1+\varepsilon)n$. Pak jsme ukázali metavětu o simulacích časové složitosti zkoumáním stromu výpočtů a prostorové simulaci zkoumáním grafu konfigurací. Ukázali jsme, jak tyto metavěty použít pro ukázky vztahů mezi D/NTime a D/NSpace a naopak.
Tvrdil jsem, že pro důkazy těchto vět by se nám hodila konstruovatelnost funkcí. Nejspíš je ale možné provést simulace tak, že nejprve zkoušejí pracovat s omezenými prostředky, postupně jich přidávají víc a víc, a tím se dá u těcht vět předpokladu s konstruovatelností vyhnout.
Cvičení 5
Konstatoval jsem, že přednáška je oproti loňsku příliš pozadu a potřebujeme již cvičit NP-úplnost. Začali jsme alespoň zadáním příkladů porovnávání tříd (N/D)(Time/Space)$(f(n))$. Pro $f(n)\in\{n,n\log n,n^3,2^{n^3}\}$. Jednalo se o pokusy o uplatnění metavěty o simulacích časové resp. prostorové složitosti. Museli jsme si dát pozor na rozdíl v použiti $O()$ normálně a v exponentu.
Zajímavé na porovnáváních je podívat se na ostrost inkluzí. Konstatoval jsem, že i zde je přednáška příliš pozadu a nezbylo mi než vyslovit (a dokázat) věty o hierarchii (pro DSpace, NSpace a DTime, existenci Žákovy věty pro NTime jsem naznačil, ale nedokazoval) (metavěta o diagonalizaci, natahování).
S těmito větami se nám podařilo ve většině případů ukázat ostrou nerovnost. Výjimkou byl pouze případ, kdy na obou stranách bylo stejné $f$. Vždy bylo lepší, když to šlo, použít prostorové věty o hierarchii, protože stačilo kvůli ostré nerovnosti zvětšit funkci jen nepatrně.
Upozornil jsem na technická úskalí při skládání prostorově omezených transformací, i na obdobný problém s časem při rozdvojení vstupu na simulované slovo a kód stroje. Tím byly zdůvodněny předpoklady $s,s'\ge \log n$ a $t,t'\ge (1+\varepsilon)n$.
Na konci hodiny jsem ještě naznačil, jak se vypořádat se vztahem DTime$(2^n)$ a DTime$(2^n\sqrt n)$ pomocí natahovacích vět. (Ve větě o hierarchii ke sporu potřebujeme $t'\not\in O(t\log t)$, takže potřebujeme mezeru před tím nějak ponatahovat).
Cvičení 6
Tématem cvičení byla NP-úplnost a převoditelnost.
Nejprve jsem ukázal typickou metodu na důkaz těžkosti jiných NP jazyků. Ukážeme, že v jazyku dokážeme zapsat boolovské proměnné a jejich negace, dokážeme, že jsme schopni v jazyku zachytit nezávisle jednotlivé klauzule SATu. Příkladem byl důkaz NP-těžkosti barvení grafu 3mi barvami (který studenti znali). Deklarační trojúhelník na pojmenování barev, deklarační trojůhelníky sdílející nebooleovskou barvu deklarují vždy proměnnou a jejich negaci. Dva trojúhelníky spojené hranou a připojené hranami ke třem literálům a FALSE umožňují doobarvení, právě když ty čtyři vrcholy nemají stejnou barvu (ty 3 literály nejsou současně FALSE). Takto jsme schopni vytvořit klauzule. Pokud najdeme obarvení grafu, obarvení význačných vrcholů definuje pravdivost a při ní jsou všechny klauzule pravdivé. Naopak, pokud někdo nalezne ohodnocení proměnných, pro něž je formule pravdivá, můžeme podle něj obarvit příslušné vrcholy a i vrcholy podgrafů odpovídajících klauzulím bude možno doobarvit.
Dalším příkladem byl Plesníkův důkaz NP-těžkosti hledání Hamiltonovské kružnice v orientovaném grafu. Dokonce v bipartitním grafu s celkovým stupněm vrcholů 3, kde v jedné partitě je indegree 1 a v druhé outdegree 1. Jako bonus jsme slíbil to, že budeme umět graf udělat rovinný. Jako proměnná nyní sloužila rozbočka vložená na hranu, která určitě leží na HK. Pokračování jedním směrem znamená ohodnocení true, druhým směrem false. Ukázali jsme konstrukci pro nonekvivalentítko toho, zda po cestě od rozbočky HK vede. Následně jsme ukázali jak propojit kružnici reprezentující klauzuli s rozbočkami literálů klauzule. Pokud ani jeden z literálů nebude pravdivý, kružnice zůstanou izolované a nedostaneme Hamiltonovskou kružnici. Propojky byly navrženy tak, aby bylo z jakéhokoli pravdivého literálu možno odbočit do kružnice klauzule, aby z kružnice klauzule bylo možno projít odbočku nepravdivého literálu, a aby v případě dalšího pravdivého literálu bylo možno projít část vrcholů konstrukce z literálu a zbytek z kružnice klauzule. Pokud je formule splnitelná, určí nám splňující ohodnocení proměnných výběr v rozbočeních proměnných a tím i literálech klauzulí, konstrukce klauzulí umožňuje prvním pravdivým literálem kružnici klauzule s hlavní kružnicí propojit a ostatními literály kružnice nerozpojit. Pokud nalezneme Hamiltonovskou kružnici, rozbočky v oblasti proměnných nám definují ohodnocení proměnných a protože jsou kružnice klauzulí napojeny na HK, musí být pro toto ohodnocení klauzule pravdivé a tedy formule splněna.
Konstrukci je možno zjednodušit tak, aby nebylo potřeba posledního popsaného průchodu, pokud bychom převáděli z „1 in 3 SATu“. Komplikuje se pak ale argumentace toho, že nemáme řešení kružnice, pokud je formule nesplnitelná (resp. nesplněná pro dané ohodnocení proměnných). Problém s kterým se musíme vypořádat, je případ 3 pravdivých literálů v klauzuli. Zůstane v takovém případě část kružnice klauzule oddělena od hlavní kružnice?
O „1 in 3 SATu“ jsme si ukázali, že je také NP-úplný. Zformulovat v něm garvení grafu 3-mi barvami bylo velice jednoduché. (Ani nevím, jak bych převod ze SAT dělal bez použití mezikroku s barvením.) (Vzhledem k tomu, že „1 in 3 SAT“ je možno formulovat jako speciální případ celočíselného lineárního programování, víme, že tento zobecněný problém je taky NP-úplný.)
Pak jsme si pohráli se SAT a redukcí počtu výskytů proměnných a následně s redukcí délek klauzulí. Vždy jsme ukázali, že při další redukci již vzniká problém, který jsme schopni deterministicky v polynomiálním čase řešit.
Pak jsme se věnovali různým variantám kachličkování. Jak je to s jednobarevnými stěnami koupelny? Jak je to s jednobarevnou celou koupelnou (rozměry v unární sopustavě!)? (Co když nejsme schopni zajistit, aby dělníci kachlíky neotáčeli? U průhledných kachliček nepřevraceli?) Co se stane, pokud nebude dán katalog kachlíků, ale seznam již nakoupených kachlíků?
Cvičení 7.1.2019
Na posledním cvičení jsme si trochu hráli s aproximacemi, (trochu s UPAS pro batoh), pak jsme si hráli s barvením rovinných grafů 3mi barvami a redukcí stupňů vrcholů. Ke konci jsme narazili na to, zda problém celočíselného programování je vůbec v NP, jediné co jsme poradil je nesnažit se ukázat, že neexistují velká řešení, ale místo toho ukazovat, že s každým velkým řešením existuje i řešení menší.
Úplně na konci jsme zabrousili k polynomiální hierarchii a #P-těžkosti, PP-úplnosti a pravděpodobnostním třídám.