Vladan Majerech - NTIN090 Základy složitosti a vyčíslitelnosti
Last Modified: 12.11.2026
Index
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 středečního cvičení a termín na jejich odevzdání bude u úkolu explicitně uveden (nejspíš čt 15:40). 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 pojmy display, akce, krok, konfigurace. 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. Definovali jsem časovou a prostorovou složitost. Definovali jsme i nedeterministické stroje.
Nejprve 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é pásce (s reprezentací pásek za sebou či prokládaně), 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)$. (I) kvůli různým definicím prostorové složitosti jsme pak 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$).
Na prvním cvičení jsme zapomněli odhadnout počty možných konfigurací stroje s omezenou prostorovou složitostí pro pevný vstup (stroje bez výstupních pásek).
Následně jsme zmínili problém jednostranně nekonečné pásky. Taky jsme se zabývali problémem děrné pásky, resp. 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 nejvýš 2 a později nejvýš jednu podakci), ale nebyl čas se mu věnovat. Na poslední verzi cvičení jsem nezapomněl spočítat počet konfigurací, které mohou nastat pro daný vstup velikosti $n$, pokud má stroj danou prostorovou složitost $s(n)$ (vyšlo to $2^{O(s(n))+\log n}$).
Cvičení 2
Nejprve jsme se věnovali určení velikostí množin abeceda, slovo, jazyk. Abeceda je konečná, množina slov je spočetná (ukázali jsme jak očíslovat slova nad abecedou velikosti 2, a obdobně pro jiné velikosti). Ukázali jsme, ž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ý). Definovali jsme bijekci mezi čísly a slovy nad dvouprvkovou abecedou, definovali jsme bijekci (několik možností) mezi uspořádanými dvojicemi čísel a čísly.
Pak 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. Použili jsme již druhou „datovou strukturu“ na Turingově stroji.
Dále jsme si pro účely cvičení definovali bylo „disjunktní sjednocení“ $\oplus$. Dále jsme pracovali s pojmy $\leq_m$ (a $\leq_T$) převeditelnosti. Ukázali jsme si $A\leq_m A\oplus B$ i to, že z $A\leq_m C$ a $B\leq_m C$ plyne $A\oplus B\leq C$, taky jsme zjistili co plyne z předpokladu $A\leq_m \overline{A}$ pro rekurzivně spočetný jazyk $A$ a jeho doplněk $\overline{A}$ o rozhodnutelnosti $A$ (je přijímán strojem, který se vždy zastaví).
Cvičení 3
Nejprve jsme se věnovali vyčíslitelnosti, udělali jsme převod $L_u=\{\langle x,y\rangle\mid y\in L_x\}$ na $\hbox{Inf}=\{m\mid |L_m|=\infty\}$ a $J=L_u \oplus \overline L_u$ na $EQ=\{\langle m,n\rangle \mid L_m=L_n\}$.
Následně jsme se věnovali složitosti. Začali jsme triviálními inkluzemi, kde k důkazu inkluze stačí použít tentýž stroj. Pokračovali jsme metavětami o simulacích nedeterministických výpočtů. Buď jsme si pomohli posloupností dvojic display, akce, pak zjišťováním dosažitelností vrcholů v grafu konfigurací. Prohledávání grafu jsme dělali nejprve co nejrychleji, ale potřebovali jsme exponenciální čas vůči prostoru původního stroje (minimálně však polynomiální vůči velikosti vstupu.) Pak jsme řešili deterministicky prostorově efektivní prohledávání grafu (kvadratický prostor vůči původnímu prostoru, přinejmenším však kvadrát logaritmu velikosti vstupu. Savitchova věta.) (Rodina Waltera Johna Savitche žila v USA přinejmenším od třicátých letech dvacátého století, takže k transkripci jména došlo dávno před vyslovením příslušné věty.) Nakonec jsme ještě ukázali, nedeterministicky prostorově efektivní prohledávání grafu, kde výpočet výsledněho stroje vždy buď "zfailuje" nebo vydá správnou odpověď. Vždy aspoň jedna větev výpočtu doběhne. Stačí nám k tomu stejně velký prostor (můžeme tak ve stejném prostoru negovat náležení do jazyka) Immerman-Szelepcscényi.
Naznačil jsem, že se nám bude pro důkazy hodit konstruovatelnost funkcí. (Při všech simulacích jsme museli provést nějakou alokaci, a to by mohla být nejnáročnější část výpočtu. Pokud by funkce omezující simulovanou třídu byla konstruovatelná, je vše bez problémů. Pokud bychom ji dokázali spočítat prostředky simulující třídy, tak to taky není problém. V případě prostorově omezené simulující třídy můžeme postupovat tak, že alokovaný prostor postupně inkrementujeme, tím dostáváme řešení pro slova patřící do jazyka ...) Příští hodinu se konstruovatelnosti budeme věnovat víc.