Vladan Majerech - NTIN090 Základy složitosti a vyčíslitelnosti
Last Modified: 12.9.2022
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 cvičení a termín na jejich odevzdání je do počátku 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 | 25.10.2021 | 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 | 8.11.2021 | 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 | 8.11.2021 | 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 | 22.11.2021 | 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 | 22.11.2021 | Je jazyk $\hbox{Size}=\{\langle M,k\rangle\mid |L(M)|\ge k\}$ rozhodnutelný? Je částečně rozhodnutelný? | |||||||||
| inkluze | 3 | 6.12.2021 |
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).
| |||||||||
| 3Dvěže | 3 | Dokažte, že je NP úplné zjistit, zda je možno do 3D šachovnice $k\times\ell\times m$ umístit $k\cdot\ell$ věží tak, aby se navzájem neohrožovaly. Přitom jsou některá políčka označena kaňkou a na tato políčka je zakázáno umístit věž. Věž na políčku $(x,y,z)$ ohrožuje všechna políčka, která se od $(x,y,z)$ liší právě v jedné souřadnici. |
V následující tabulce je uveden aktuální stav získaných bodů jednotlivých studentů.
| Id studenta | celkem | detail |
|---|---|---|
| L | 9.5 | reset(3), prime(1), $\exists\forall$(0), reg(1), size(1+1/2), inkluze(3) |
| a | 4 | reset(0), $\exists\forall$(2), prime(1), reg(0), size(1) |
| l | 2 | reset(2) |
| p | 1 | reg(1) |
| A | 11 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(2) |
| B | 13 | reset(3), prime(1), $\exists\forall$(2), reg(1), size(2), inkluze(4) |
| C | 13 | reset(3), $\exists\forall$(1), prime(1), reg(1), size(2), inkluze(5) |
| D | 11 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(1), inkluze(3) |
| E | 11 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(2) |
| F | 14 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(5) |
| G | 11 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(2) |
| H | 15 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(6) |
| I | 14 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(5) |
| J | 14 | reset(3), $\exists\forall$(2), prime(1), reg(0), size(2), inkluze(6) |
| K | 14 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(5) |
| M | 13 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(4) |
| N | 10 | reset(3), $\exists\forall$(2), prime(1), reg(0), size(2), inkluze(2) |
| O | 13 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(4) |
| P | 12 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(1), inkluze(5) |
| Q | 10 | reset(3), $\exists\forall$(2), prime(0), reg(1), size(1), inkluze(3) |
| R | 15 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(6) |
| S | 12 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(3) |
| T | 10 | reset(3), $\exists\forall$(0), prime(1), reg(1), size(1), inkluze(4) |
| U | 13 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(4) |
| V | 11 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(2) |
| W | 11 | reset(3), $\exists\forall$(1), prime(0), reg(1), size(2), inkluze(4) |
| X | 10 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(1) |
| Y | 14 | reset(3), prime(1), $\exists\forall$(2), reg(1), size(1), inkluze(6) |
| Z | 10 | reset(3), $\exists\forall$(1), prime(1), reg(1), size(2), inkluze(2) |
| b | 11 | reset(3), $\exists\forall$(1), prime(1), reg(1), size(2), inkluze(3) |
| c | 12 | reset(3), $\exists\forall$(1), prime(1), reg(1/2), size(1/2), inkluze(6) |
| d | 10 | reset(3), $\exists\forall$(0), prime(1), reg(1), size(2), inkluze(3) |
| e | 15 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(6) |
| f | 10 | reset(3), prime(1), reg(1), size(2), inkluze(2), $\exists\forall$(2/2) |
| g | 11 | reset(3), $\exists\forall$(1), prime(1), size(1+1/2), reg(1/2), inkluze(4) |
| h | 15 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(6) |
| i | 12 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(1), inkluze(4) |
| j | 10 | reset(3), inkluze(5), $\exists\forall$(2/2), size(2/2) |
| k | 12 | reset(3), reg(1), size(2), inkluze(6) |
| m | 15 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(6) |
| n | 15 | reset(3), $\exists\forall$(2), prime(1), reg(1), size(2), inkluze(6) |
| o | 10 | reset(3/2), prime(1), $\exists\forall$(1/2), reg(1), size(2), inkluze(3+2/2) |
Odkazy na obdobné stránky
Cvičení Petra Kučery, Petra Gregora a moje loňská.
Cvičení 1
Na první verzi 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, krok. Definovali jsme i nedeterministické stroje. Na první verzi cvičení jsme se letmo věnovali počáteční konfiguraci, daleko víc nás zajímal průběh výpočtu, ani jsme se nevěnovali tomu, jak je definován konec výpočtu. Nezadefinovali jsme co je prostorová a co časová složitost. Na druhé verzi cvičení jsme kralové podmínky i co je jaká složitost zmínili.
Zabývali jsme se možností redukce počtu pásek 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 se chvíli věnovali problému jednostranně nekonečné pásky. Pak problému 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 akci). Zabývali jsme se i problémem děrné pásky, tedy situací, kdy na pásku můžeme zapisovat nejvýše 2 krát, později nejvýše jednou.
Na druhé verzi cvičení jsme velmi líného hardvéráře jen zmínili, bez náznaku řešení, zato jsme se na konci hodiny věnovali trochu RAMU (diskusi náročnosti definice časové složitosti na RAMu).
Cvičení 2
Nejprve 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.
Pak jsme si definovali základní pojmy jako abeceda, slovo jazyk, věnovali se určení velikosti příslušných množin. Abeceda je konečná, množina slov je spočetná (ukázali jsme jak očíslovat slova nad abecedou velikosti 2, pro jiné velikosti by bylo obdobné). Následně jsme ukázali, ž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ý).
Dále jsme se zabývali bijekcí mezi kartézským součinem přirozených čísel a přirozenými čísly. Další pojem, který jsme si pro účely cvičení definovali bylo „disjunktní sjednocení“ $\oplus$. Nejprve jsme použili jednu definici, ukázali si vlastnosti a následně jsme se bavili o možnosti alternativní definice, stejných vlastností. Dále jsme pracovali s pojmem $\leq_m$ převeditelnosti. Ukázali jsme si $A\leq_m A\oplus B$ i to, že z $A\oplus B\leq_m C$ plyne $A\leq C$.
Pak jsme si chvíli hráli se kombinováním rekurzivně spočetných jazyků (zřetězení, iterace) (pro rekurzivní není žádná komplikace). Základní trik připomíná iterative deepening (jednotlivé simulace pouštíme s omezenými prostředky s tím, že postupně povolujeme více a více prostředků).
Ke konci jsme si ukázali, že z $A\leq_m \overline{A}$ pro rekurzivně spočetný jazyk $A$ a jeho doplněk $\overline{A}$ plyne jeho rekurzivnost (je přijímán strojem, který se vždy zastaví). Skončili jsme důkazem toho, že jazyk $J=L_u\oplus \overline{L_u}$ není rekurzivně spočetný (kde $L_u=\{(M,x)\mid M\hbox{ přijímá }x\}$ je univerzální jazyk).
Cvičení 3
Věnovali jsme se různým převodům $\leq_m$ především z $L_u$. Převáděli jsme na $EQ=\{\langle M,N,\rangle\mid L_M=L_N\}$, jeho doplněk, $Inf=\{M\mid |L_M|=\omega\}$.
Ke konci hodiny jsme definovali pojmy ze složitosti a povídali si o lineární kompresi a zrychlení. Na druhé verzi cvičení jsme ještě převáděli $L_u$ na Postův korespondenční problém.
Cvičení 4
Na první verzi cvičení jsme nejprve doplnili převod $L_u$ na Postův korespondenční problém a pak jsme se věnovali složitostním třídám. Stihli jsme použití časové metavěty na simulaci nedeterministického výpočtu v čase $f(n)>(1+\varepsilon)n$ univerzálním strojem v čase $f$ (nedeterministická redukce počtu pásek), simulaci stroje garantujícího $L\in\mathrm{NTime}(f)$ prostředky garantujícími $L\in\mathrm{Space}(f)$. Použití prostorové metavěty jsme ukázali simulaci stroje garantujícího $L\in\mathrm{NSpace}(f)$ jak pomocí stroje garantujícího $L\in\mathrm{Time}(2^{O(f+\log n)})$, tak pomocí stroje garantujícího $L\in\mathrm{Space}((f+\log n)^2)$. Pak jsme ukázali ještě převod na stroj přijímající stejný jazyk se stejnými prostředky (nedeterministicky v prostoru $f$), ale výsledný stroj se na každém vstupu zastaví a některá větev výpočtu řekne ANO nebo NE. Všechny větve výpočtu (pro daný vstup), které vydají odpověď se na odpovědi shodnou. Tento převod je možno použít k definici stroje přijímajícího doplněk jazyka. Trošku jsme u převodů zanedbali diskusi potřeby konstruovatelnosti použitých funkcí.
V posledních minutách zazněla trojvěta o hierarchii (i trojjazyk, který ji dokazuje), nebyl ale čas zkontrolovat, že příslušný jazyk má požadované vlastnosti (a platí to až po přehození indexů $_1$,$_2$). Na druhé verzi cvičení jsme už nemuseli řešit PKP a trojvětu o hierarchii jsme probrali celou (mírně jsme přetáhli). Taky jsem trošku víc upozorňoval na užitečnost konstruovatelnosti v důkazech inkluzí.
Cvičení 5
Nejprve jsem dokončil věty o hierarchii, včetně Žákovy věty pro nedeterministickou časovou hierarchii. Pak jsme si povídali o NP-úplných problémech a převodech mezi nimi.
Cvičení 6
Věnovali jsme se NP-úplnosti a převodům mezi NP-úplnými problémy.
Cvičení 7
Věnovali jsme se #P-úplnosti a převodům mezi #P-úplnými problémy. #SAT, #3SAT, #k VP, Perm(-1,-1/2,0,1/2,1), Perm (-2,-1,0,1,2), několik Perm (p-2,p-1,0,1,2), Perm (0,1). Při převodu z VP na permanent -1, -1/2, 0, 1/2, 1 matice se nárůst počtu řešení na rozdíl od převodu na HK změnil z $k!(k-1)!$ na $(k!)^2$.
Ke konci hodiny jsem ukazoval jak zkonstruovat prostorově nekonstruovatelnou funkci (Důsledek Borodinovy věty o mezerách). Trošku matoucí mohlo být, že jsem říkal, že bude malá. Pravdivější tvrzení je, že pracovní prostor potřebný pro její výpočet je vždy mnohem větší než její funkční hodnota.