Vladan Majerech - NTIN090 Základy složitosti a vyčíslitelnosti
Last Modified: 2.2.2021
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
E-mailem již byste měli mít link na google doc, kde je link na zoom. Pokud byste e-mail nedostali a měli, ozvěte se mi e-mailem. Nemusíte striktně chodit na cvičení (l/s) podle rozvrhu, pokud víte, že nebudete na svoje cvičení moct přijít a máte šanci navštívit cvičení opačné, tak to využijte.
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 ve středu liché i sudé týdny. Úkoly jsou zadávány brzy po prvním středčním cvičení a termín na jejich odevzdání je do počátku středeční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í | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| reset | 3 | 21.10.2020 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. | |||||||||
| $\exists\forall$ | 2 | 4.11.2020 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 | 4.11.2020 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 | 25.11.2020 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 | 25.11.2020 10:40 | Je jazyk $\hbox{Size}=\{\langle M,k\rangle\mid |L(M)|\ge k\}$ rozhodnutelný? Je částečně rozhodnutelný? | |||||||||
| inkluze | 3 | 16.12.2020 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).
| |||||||||
| 1 in 3 SAT | 3 | 6.1.2021 10:40 | Dokažte, že jazyk seznamů trojic literálů $a:\{1,2,\dots,m\}\times\{1,2,3\}\to \{\neg,\lambda\}\times\{1,\dots,k\}$, kde existuje $(x_1,x_2,\dots,x_k)\in \{0,1\}^k$, tak, že pro každé $i\in \{1,2,\dots,m\}$ platí $f(a_{i,1})+f(a_{i,2})+f(a_{i,3})=1$, kde $f((\lambda,k))=x_k$ a $f((\neg,k))=1-x_k$, je NP-úplný. |
V následující tabulce je uveden aktuální stav získaných bodů jednotlivých studentů.
| Id studenta | celkem | detail |
|---|---|---|
| G | 3 | reset(3) |
| K | 3 | reset(3) |
| O | 0.9 | reset(0), $\exists\forall$(0), prime(0.9) |
| Q | 1.5 | reset(0+3/2), $\exists\forall$(0), reg(0) |
| S | 8 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(1) |
| T | 5.5 | reset(3), $\exists\forall$(0), prime(1), 1in3SAT(3/2) |
| Y | 1.5 | reset(3/2) |
| Z | 0 | reset(0) |
| f | 0 | reset(0) |
| h | 0.5 | reg(0/2), size(1/2) |
| A | 10 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(1) |
| B | 12 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(3) |
| C | 14 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(5) |
| D | 14 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(5) |
| E | 11 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(1), inkluze(3) |
| F | 10 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(1) |
| H | 15 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(6) |
| I | 11 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(2) |
| J | 17 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(5), 1in3SAT(3) |
| L | 13 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(4) |
| M | 14 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(5) |
| N | 13 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(4) |
| P | 10 | reset(3), prime(1), reg(1), size(2), inkluze(3) |
| R | 12 | reset(3), $\exists\forall$(0), reg(1), size(2), inkluze(6) |
| U | 12.5 | reset(3/2), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(5) |
| V | 10 | reset(3), $\exists\forall$(1), prime(1), reg(1), size(1), 1in3SAT(3) |
| W | 12 | reset(3/2), $\exists\forall$(2), prime(1), reg(1/2), size(2), inkluze(2), 1in3SAT(3) |
| X | 11 | reset(3), $\exists\forall$(1), prime(1), reg(1), size(2), inkluze(3) |
| a | 10.5 | reset(0+3/2), $\exists\forall$(0), prime(1), reg(1), size(2), inkluze(5) |
| b | 10.5 | reset(3/2), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(3) |
| c | 11 | reset(3), $\exists\forall$(1), prime(1), reg(1), size(1), inkluze(4) |
| d | 13 | reset(3), $\exists\forall$(0), prime(1), reg(1), size(2), inkluze(6) |
| e | 10.5 | reset(3/2)$\exists\forall$(1), prime(1), reg(1), size(2), inkluze(1), 1in3SAT(3) |
| g | 10 | reg(1), size(1+1/2), 1in3SAT(3), reset(3/2), $\exists\forall$(2/2), prime(1/2), inkluze(3/2) |
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 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.
Na první verzi cvičení jsme nehovořili o nedeterministických strojích. Nediskutovali jsme počáteční a koncové konfigurace stroje. Na druhé verzi cvičení trochu toho zaznělo.
Řešili jsme úlohu „líných hardwareářů“, jak transformovat přechodovou funkci jednopáskového stroje tak, aby nikdy neprováděl současně 3 z podakcí změň písmeno na pásce, změň stav, změň polohu. Úlohu, kdy je možno provádět nejvýš jednu z podakcí jsme řešit na první verzi cvičení nezačali a na druhé nedokončili.
Zabývali jsme se problémem redukce počtu pásek, vymysleli jsme řešení s časovou složitostí redukce se zpomalením $O(n)$. Zpomalení jen $O(\log n)$ jsem naznačil na konci první verze a v průběhu verze druhé.
Domácí úkol výjimečně zadávám až po prvním cvičení druhé skupiny, (další domácí úkoly budu zadávat po prvním cvičení první skupiny).
Na druhé verzi cvičení jsme ještě řešili jednostrannou nekonečnost pásky.
Cvičení 2
Věnovali jsme se ekvivalenci RAM a TS, následně jsme si připoměli základní pojmy co to je abeceda, slova a jazyky. Ukázali jsme si, že jazyků je nespočetně, zatímco programů spočetně (a ukázali jsme že jazyk $K=\{w_i\mid w_i\not\in L_i\}$ není rozpoznáván žádným TS). Věnovali jsme se standardnímu číslování slov a možnosti kódování uspořádaných dvojic či n-tic. Na úplném konci jsme zmínili převoditelnost a zformulovali úlohu o převeditelnosti mezi $L_1$ a $L_1 \oplus L_2$. Na druhé verzi cvičení jsme si místo s $\oplus$ hráli s uzavřeností částečně spočetných množin na zřetězení a iteraci.
Cvičení 3
Na první verzi cvičení jsme se věnovali $\le_m$ převoditelnosti, jak s $\oplus$, tak s $J=L_u\oplus \overline{L_u}$ ($J\le_m\overline{J}$), pak jsme převáděli $L_u$ na $EQ=\{\langle M,N\rangle\mid L_M=L_N\}$ či ${\rm Fin}=\{M\mid L_M{\rm\ je\ konečný}\}$ či jejich negace.
Na druhé verzi cvičení (studenti se po státním svátku prolínají, takže to číslování hapruje) jsme se věnovali vztahům mezi (D/N)(Time/Space). Nejprve jsme si dokázali tvrzení o lineární kompresi a o lineárním zrychlení (pro $t>(1+\epsilon)n$). Hlavní byly dvě metavěty o simulování ... metavěta o simulování výpočtu omezeného časem $t$ pomocí zkoumání posloupností délek $t$ dvojic (display,akce), metavěta o simulování výpočtu omezeného prostorem $s$ pomocí dosažitelnosti nějaké přijímací konfigurace z počáteční konfigurace v grafu konfigurací omezených prostorem $s$. Metavěty jsme aplikovali jak na vztah mezi NTime a DSpace, tak na vztahy mezi NSpace a Dtime či DSpace. První metavětu jsme aplikovali i na redukci počtu pásek nedeterministického výpočtu. Druhou metavětu je možno aplikovat na NSpace(s) program a zajistit, abychom dostali stejný výstup ve stejném prostoru, ale aby se navíc všechny výpočty zastavily. K tomu jsme se na cvičení nedostali.
Více pozornosti si zasloužil důkaz vztahu mezi NSpace a DSpace, kde realokace prostoru nám umožnila zkontrolovat existenci sledu délky $2^\ell$ jen s použitím prostoru pro $\ell+2$ konfigurací. Čas takovéto simulace pak je až $(2^\ell)^{2^\ell}$, kde $\ell\in O(s+\log n)$, ale to nás netrápí.
Na úplném konci hodiny jsme definovali konstruovatelné funkce, s nimiž je možno metavěty o simulacích bezproblémově použít.
Cvičení 4
Na první verzi cvičení jsme se věnovali vztahům mezi (D/N)(Time/Space). Nejprve jsem naznačil, že existují pojmy časově resp. prostorově konstruovatelných funkcí. Pak jsme si dokázali tvrzení o lineární kompresi a o lineárním zrychlení (pro $t>(1+\epsilon)n$). Hlavní byly dvě metavěty o simulování ... metavěta o simulování výpočtu omezeného časem $t$ pomocí zkoumání posloupností délek $t$ dvojic (display,akce), metavěta o simulování výpočtu omezeného prostorem $s$ pomocí dosažitelnosti nějaké přijímací konfigurace z počáteční konfigurace v grafu konfigurací omezených prostorem $s$. Metavěty jsme aplikovali jak na vztah mezi NTime a DSpace, tak na vztahy mezi NSpace a Dtime či DSpace. První metavětu jsme aplikovali i na redukci počtu pásek nedeterministického výpočtu.
Více pozornosti si zasloužil důkaz vztahu mezi NSpace a DSpace, kde realokace prostoru nám umožnila zkontrolovat existenci sledu délky $2^\ell$ jen s použitím prostoru pro $\ell+2$ konfigurací. Čas takovéto simulace pak je až $(2^\ell)^{2^\ell}$, kde $\ell\in O(s+\log n)$, ale to nás netrápí.
Druhou metavětu jsme aplikovali i na NSpace(s) program a zajistili, abychom dostali stejný výstup ve stejném prostoru, ale aby se navíc všechny výpočty zastavily. Díky tomu víme, že je NSpace(s) uzavřené na doplňky a ke stroji M přijímajícím v NSpace(s) jazyk L jsme schopni (algoritmicky) sestrojit stroj M' přijímající doplněk L.
Na druhé verzi cvičení jsme se věnovali větám o hierarchii. Jak DTime, DSpace, tak NSpace jedním společným důkazem. U NSpace jsme potřebovali doplnit techniku transformace programu na program pro negaci jazyka, aniž bychom zvětšili prostorovou náročnost. Museli jsme upozornit na techniku skládání prostorově nenáročných konfigurací i techniku časově nenáročného rozdvojení vstupu. To vynutilo předpoklady $s>\log n$ a $t>(1+\epsilon)n$. U NTime jsem naznačil že existuje Žákova věta, použitelná pro podobné účely. Taky jsem naznačil konstrukci nekonstruovatelných funkcí pomocí Borodinovy věty a zdánlivé paradoxy plynoucí z použití nekonstruovatelných omezení nároků.
Ve zbytku hodiny jsme se věnovali NP-úplnosti. Velice rychle jsme prolítli Hamiltonovské kružnice/cesty, naznačil jsem užitečnost znalosti těžkosti HK v grafech s malými stupni vrcholů a velice rychle jsem naznačil Plesníkův důkaz tohoto tvrzení (použil jsem techniku převodu ze SAT ukazující možnost simulovat boolovskou hodnotu, existenci konstrukce pro neekvivalenci hodnot a existenci konstrukce pro klauzuli (nezávislou na ostatních klauzulích)).
Cvičení 5
První verze cvičení se od druhé verze čtvrtého cvičení lišila jen v tom, že důkaz negování v NSpace byl již z minula, a co se týče NPC jsme se úlohám s kružnicemi a cestami věnovali. Nestihl jsem tak motivaci ke kružnicím s malými stupni. (Cesta dlouhá alespoň k na čtverečkové síti se zakázanými čtverečky. Kachlíkování ve variantě je dán seznam kachlíků, které je možno otáčet a vybíráme podseznam, který použijeme k vydláždění koupelny (přiléhající barvy musí být vždy shodné).)
Na druhé verzi cvičení jsme si hráli s hledáním nezávislých množin, s barvením grafu a batohem. Ke konci jsem ukázal důkaz že kachlíkování, kde kachlíky leží na místě a je potřeba je jen pootáčet je těžké i v případě použití jen 4 druhů kachlíků.
Cvičení 6
Na posledním cvičení jsem trochu povídal o #P (jeho vztahu k PP a o permanentu 0-1 matice). Hlavně jsem ale velice rychle shrnul důležitá fakta z celého semestru a vyzkoušeli jsme si vzorovou písemku.
Na důkaz #P těžkosti permanentu zbylo velice málo času, takže jediné co bylo řečeno relativně pořádně byl převod k-VP na orientovanou HK, kde známe vztah mezi počtem řešení k-VP a počtem řešení oHK.
V řetězci tvrzení bychom ještě museli upozornit, že převod z SAT na k-VP zachovával počet řešení.
Jen jsem naznačil, že pro daný konkrétní graf oHK odpovídající obecnému k-VP jsme schopni nahradit v matici sousednosti nějaké podmatice podmaticemi s hodnotami od -1 do 1 v násobcích 1/2 tak, aby peranent výsledné matice místo počtu rozkladů na cykly původního grafu počítal počty oHK v daném grafu.
Poloviny nejsou problém, stačí vynásobit prvky matice dvojkou, takže známe vztah velikosti výsledného permanentu s počtem původních k-VP.
Komplikovanější je zbavit se záporných čísel. Další krok je spočítat permanent modulo součin polynomiálně mnoho prvočísel z počátečního úseku prvočísel (součin je dostatečný na jednoznačné rozlišení všech možných nejvýš $2\cdot 2^nn!$ výsledků). Předposlední krok je výpočet modulo jedno polynomiálně velké prvočíslo. Nyní již nejde o těžkost pomocí transformace, ale pomocí redukce (potřebujeme zavolat více podproblémů ... čínská věta o zbytcích). Posledním krokem je pomocí 0-1 matice počítat permanent celočíselné matice mod polynomiálně velké prvočíslo. K tomu stačí každou souřadnici interpretovat jako číslo od $0$ do $p-1$, šikovným nafouknutím matice pak dostaneme 0-1 matici rozměrů nejvýš $n+pn^2$, která má mod $p$ stejný permanent.
Počet k-VP jsme tedy schopni spočítat na základě polynomiálně mnoho výpočtů permanentů polynomiálně velkých 0-1 matic. (viz poslední kapitola skript z Úvodu do Složitosti ....)