NTIN090 - Úvod do složitosti a vyčíslitelnosti

Petr Kučera, KTIML MFF UK

Zimní semestr 2016/2017

Petr Kučera

Obsah

  1. Odkazy a dokumenty
  2. Zkouška
  3. Zápočty
  4. Obsah letošních přednášek
  5. Obsah mých letošních cvičení
  6. Vzorová zkoušková písemka (stav roku 2015/16)

Odkazy a dokumenty

Zkouška

Zatím je popsán stav školního roku 2015/16.

Ráno v 9:00 se píše písemka, trvá 60 minut a budu v ní zadávat 3 příklady. Ty budou stylem podobné příkladům, jež byly řešeny na cvičeních. K dispozici je vzorová zkoušková písemka. Ihned po napsání písemky začne ústní zkouška, několik studentů zůstane na ústní zkoušku ihned, ostatním přidělím pozdější čas. Pro připuštění k ústní části zkoušky je nutné mít alespoň jeden příklad správně. Při ústní části zkoušky si vylosujete jednu z otázek náhodně.

Klasifikace bude určena na základě písemné i ústní části. Obě části budou bodované. Dohromady je možno získat až 100 bodů, přičemž

Zápočty

Následující informace se vztahují pouze k mým pondělním cvičením, podmínky udělení zápočtu na čtvrtečních cvičeních si určuje kolega Majerech sám.

Po každém cvičení zadám dva až tři domácí úkoly, které budou dohromady za 3 body. Řešení domácích úkolů bude třeba odevzdat do začátku následujícího cvičení. Zápočet dostane ten, kdo za semestr nasbírá alespoň dvě třetiny celkového počtu bodů (tj. dvě třetiny z trojnásobku počtu cvičení). Úkoly budu zveřejňovat na této stránce (pro sudá a lichá cvičení se nejspíš budou trochu lišit) v rámci obsahu proběhlých cvičení.

Obsah letošních přednášek

1. přednáška (3. října 2016)

Slajdy 1-30. Lehký úvod do teorie algoritmů a definice Turingova stroje s příkladem (TS rozhodující jazyk palindromů).

2. přednáška (10. října 2016)

Slajdy 31-59. Převod $k$-páskového Turingova stroje na jednopáskový. RAM a jejich ekvivalence s Turingovými stroji. Kódování Turingových strojů a Gödelovo číslo.

3. přednáška (17. října 2016)

Slajdy 60-74. Univerzální Turingův stroj. Algoritmicky vyčíslitelné funkce. (Částečně) rozhodnutelné jazyky. Diagonalizační jazyk a univerzální jazyk.

4. přednáška (24. října 2016)

Slajdy 75-84. Problém zastavení. Vlastnosti (částečně) rozhodnutelných jazyků. Vyčíslitelnost (částečně) rozhodnutelných jazyků. Převoditelnost a úplnost. Úplnost univerzálního problému, problému zastavení a jeho diagonály.

5. přednáška (31. října 2016)

Slajdy 85-87. Postův korespondenční problém. Riceova věta. Zmíněna s-m-n věta.

6. přednáška (7. listopadu 2016)

Slajdy 88-105. Základní třídy složitosti. Třídy P, PSPACE, EXPTIME. Třída NP — definice pomocí polynomiálních verifikátorů, pomocí nedeterministických Turistických strojů a jejich ekvivalence. Turingovy stroje využívající menší než lineární prostor. Základní vztahy mezi třídami složitosti (zatím bez důkazu pomocné věty).

7. přednáška (14. listopadu 2016)

Slajdy 105—107. Věta o vztahu mezi nedeterministickým prostorem a deterministickým časem. Savičova věta.

8. přednáška (21. listopadu 2016)

Slajdy 108—112. Věty o hierarchii.

9. přednáška (28. listopadu 2016)

Slajdy 113—117. Polynomiální převoditelnost a NP-úplnost. NP-úplnost kachlíkování a splnitelnosti.

10. přednáška (5. prosince 2016)

Slajdy 118-123. Důkazy NP-úplnosti problémů 3-Splnitelnosti, Vrcholového pokrytí, Trojrozměrného párování. Problém Hamiltonovské kružnice byl zmíněn bez důkazu NP-pplnosti. Dále byl zmíněn problém problém Obchodního cestujícího, jehož důkaz NP-úplnosti nejspíš uvedeme později v jiném kontextu.

Obsah mých letošních cvičení

1. cvičení

  1. Sestrojte Turingův stroj, který se vždy zastaví a přijímá jazyk $L=\{a^nb^nc^n\;|\;n\geq 0\}$. Rozmyslete si jednak jednopáskový, jednak vícepáskový Turingův pro tento jazyk.
  2. Popište, jak lze převést Turingův stroj s páskou, která je potenciálně nekonečná v obou směrech na Turingův stroj, jehož páska je potenciálně nekončená pouze ve směru doprava. Můžete předpokládat, že Turingův stroj s poloviční páskou má na prvním políčku zvláštní znak zarážky (▷).
  3. Jakou třídu jazyků rozpoznávají Turingovy stroje, u nichž povolíme pohyb hlavy pouze
    1. vlevo (L) a vpravo (R),
    2. stát (N) a vpravo (R),
    3. stát (N) a vlevo (L).
  4. Ukažte, že jednopáskový Turingův stroj, který na každé políčko na pásce může zapsat nejvýš jednou (tj. nejvýš jednou může přepsat políčko jiným znakem) je ekvivalentní obyčejnému jednopáskovému TS.
  5. Ukažte, že jednopáskový Turingův stroj, který nesmí přepisovat políčka se vstupem, je ekvivalentní konečnému automatu, tedy rozpoznává právě regulární jazyky.
  6. Ukažte, že jsou-li $L_1$ a $L_2$ rozhodnutelné jazyky, pak i jazyky $L_1\cup L_2$, $L_1\cap L_2$, $\overline{L_1}$, $L_1\cdot L_2=\{uv\;|\;u\in L_1\wedge v\in L_2\}$ a $L_1^*=\{w\;|\;(\exists k\in\mathbb{N})(\exists u_1, \ldots, u_k\in L_1)[w=u_1u_2\ldots u_k]\}$ jsou rozhodnutelné jazyky.
  7. Ukažte, že jsou-li $L_1$ a $L_2$ částečně rozhodnutelné jazyky, pak i jazyky $L_1\cup L_2$, $L_1\cap L_2$, $L_1\cdot L_2$ a $L_1^*$ jsou částečně rozhodnutelné jazyky.

Domácí úkoly k 1. cvičení

  1. Ukažte, jak lze libovolný jednopáskový Turingův stroj $M$ převést na Turingův stroj $M'$, který v každém kroku provádí jen dvě ze tří možných akcí (tj. každá instrukce buď změní stav a pozici hlavy, změní stav a písmeno na pásce, nebo změní písmeno na pásce a pozici hlavy, ale neučiní všechny tyto akce najednou). [1 bod]
  2. Uvažme Turingův stroj s poloviční páskou, v němž se může hlava hýbat pouze vpravo R, nebo může vykonat pohyb RESTART, při němž se hlava vrátí na začátek pásky. Ukažte, jak převést jednopáskový TS na tuto variantu Turingova stroje. [2 body]

2. cvičení

  1. Připomenutí definic.
    • Univerzální jazyk $L_u=\{\langle M, x\rangle\;|\;x\in L(M)\}$.
    • Problém zastavení $K_0=\{\langle M, x\rangle\;|\;M(x)\!\downarrow\}$.
    • Diagonála problému zastavení $K=\{\langle M\rangle\;|\;M(\langle M\rangle)\!\downarrow\}$.
  2. Uvažme následující jazyk: $$ K_1=\{\langle M\rangle\;|\;L(M)\neq\emptyset\}\text{ .} $$
    1. Ukažte, že $K_1$ je částečně rozhodnutelný jazyk.
    2. Ukažte, že $L_u\leq K_1$.
  3. Ukažte, že $L_u\leq_m Tot$, kde $Tot=\{\langle M\rangle\;|\;L(M)=\Sigma^*\}$.
  4. Ukažte, že $L_u\leq_m Inf$, kde $Inf=\{\langle M\rangle\;|\;L(M)\text{ je nekonečný jazyk}\}$.
  5. Uvažme následující jazyk: $$ EQ=\{\langle M, N\rangle\;|\;L(M)=L(N)\}\text{ .} $$
    1. Ukažte, že $Tot\leq_m EQ$.
    2. Ukažte, že $K_1\leq_m \overline{EQ}$.
    3. Rozmyslete si, jak z předchozích dvou převodů plyne, že $EQ$ ani $\overline{EQ}$ nejsou částečně rozhodnutelné jazyky.
  6. Uvažme následující problémy ($PP$ znamená prázdná páska, $E$ existenční, $V$ všeobecný): \begin{eqnarray*} PP &=&\{\langle M, x\rangle\;|\;M(x)\!\downarrow\text{ a po ukončení výpočtu je páska $M$ prázdná}\}\\ PPE&=&\{\langle M\rangle\;|\;(\exists x)[M(x)\!\downarrow\text{ a po ukončení výpočtu je páska $M$ prázdná}]\}\\ PPV&=&\{\langle M\rangle\;|\;(\forall x)[M(x)\!\downarrow\text{ a po ukončení výpočtu je páska $M$ prázdná}]\} \end{eqnarray*}
    1. Ukažte, že problémy $PP$ a $PPE$ jsou částečně rozhodnutelné, ale nejsou rozhodnutelné.
    2. Rozmyslete si, zda je $PPV$ částečně rozhodnutelný.
  7. Uvažme následující problémy ($PS$ znamená použití stavu, $E$ existenční, $V$ všeobecný): \begin{eqnarray*} PS &=&\{\langle M, q, x\rangle\;|\;\text{$M$ použije při výpočtu nad $x$ stav $q$}\}\\ PSE&=&\{\langle M, q\rangle\;|\;(\exists x)[\text{$M$ použije při výpočtu nad $x$ stav $q$}]\}\\ PSV&=&\{\langle M, q\rangle\;|\;(\forall x)[\text{$M$ použije při výpočtu nad $x$ stav $q$}]\}\\ PS3&=&\{\langle M\rangle\;|\;(\exists x)[\text{$M$ použije při výpočtu nad $x$ stav $q_3$}]\}\\ \end{eqnarray*}
    1. Ukažte, že problémy $PS$ a $PSE$ a $PS3$ jsou částečně rozhodnutelné, ale nejsou rozhodnutelné.
    2. Rozmyslete si, zda je $PSV$ částečně rozhodnutelný.

Domácí úkoly k 2. cvičení

  1. Nechť $B$ je regulární jazyk (tj. jazyk přijímaný nějakým konečným automatem) a nechť $A$ je jazyk, pro který platí, že $A\leq_mB$, platí, že $A$ je nutně také regulární jazyk? [1 bod]
  2. Ukažte, že následující jazyk je částečně rozhodnutelný, ale nikoli není rozhodnutelný [2 body] (nepoužívejte Riceovu větu, zadání bylo opraveno, jazyk ve skutečnosti není částečně rozhodnutelný): $$S=\left\{\langle M\rangle\;|\;(\forall x\in\Sigma^*)\left[x\in L(M)\Leftrightarrow x^R\in L(M)\right]\right\}$$

3. cvičení

  1. Ukažte, že jsou-li $A$ a $B$ dva netriviální (tj. $A, B\neq\emptyset,\Sigma^*$) rozhodnutelné jazyky, pak $A\leq_mB$.
  2. Ukažte, že je-li $A$ částečně rozhodnutelný jazyk a $A\leq_m\overline{A}$, pak $A$ je ve skutečnosti rozhodnutelný jazyk.
  3. Operaci disjunktního sjednocení $\oplus$ jazyků $A$ a $B$ definujeme jako \[A\oplus B=\{a0\;|\;a\in A\}\cup\{b1\;|\;b\in B\} .\] Ukažte, že
    1. $A\leq_m A\oplus B$, $B\leq_m A\oplus B$ a
    2. je-li $C$ jazyk, pro který platí, že $A\leq_m C$ i $B\leq_m C$, pak rovněž $A\oplus B\leq_m C$.
  4. Uvažme jazyk $J=L_u\oplus \overline{L_u}$. Ukažte, že $J$ ani $\overline{J}$ nejsou částečně rozhodnutelné jazyky.
  5. Ukažte, že existuje jazyk $B$, který není částečně rozhodnutelný a $B\leq_m\overline{B}$.
  6. Uvažme jazyk \[ \mathrm{PRIME}=\{\langle p\rangle\;|\;p\text{ je prvočíslo}\} \] a jazyk \[ L_P=\{\langle M\rangle\;|\;L(M)=\mathrm{PRIME}\}\text{.} \] Ukažte, že jazyky \(L_P\) ani \(\overline{L_P}\) nejsou částečně rozhodnutelné.
  7. Rozhodněte, zda jazyk $L_S=\{\langle x, M_1, M_2\rangle\;|\;x\in L(M_1)\cup L(M_2)\}$ je rozhodnutelný, nebo alespoň částečně rozhodnutelný.

Domácí úkoly k 3. cvičení

  1. 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]\}$ (Nápověda: Vzpomeňte si na Postovu větu.) [2 body]
  2. Rozhodněte, zda jazyk $S=\{\langle M_1, M_2\rangle\;|\; L(M_1)\cap L(M_2)=\emptyset\}$ je rozhodnutelný. Pokud není rozhodnutelný, rozhodněte, zda \(S\) nebo \(\overline{S}\) je částečně rozhodnutelný jazyk. [1 bod]

4. cvičení

  1. Pro následující dvojice tříd rozhodněte, zda mezi nimi platí nějaká inkluze, pokud ano, tak zda je ostrá nebo ne. Vyznačte také dvojice, u nichž není možno (z našich znalostí) ukázat, zda mezi nimi je nějaký vztah.
    1. $\mathrm{SPACE}(n)$ $\mathrm{SPACE}(n^3)$
    2. $\mathrm{SPACE}(n^3)$ $\mathrm{TIME}(2^{(n^3)})$
    3. $\mathrm{TIME}(2^{(n^3)})$ $\mathrm{NSPACE}(n \log n)$
    4. $\mathrm{NSPACE}(n \log n)$ $\mathrm{NTIME}(n \log n)$
    5. $\mathrm{NTIME}(n \log n)$ $\mathrm{SPACE}(n)$
    6. $\mathrm{SPACE}(n)$ $\mathrm{TIME}(2^{(n^3)})$
    7. $\mathrm{SPACE}(n^3)$ $\mathrm{NSPACE}(n \log n)$
    8. $\mathrm{TIME}(2^{(n^3)})$ $\mathrm{NTIME}(n \log n)$
    9. $\mathrm{NSPACE}(n \log n)$ $\mathrm{SPACE}(n)$
    10.$\mathrm{NTIME}(n \log n)$ $\mathrm{SPACE}(n^3)$
  2. Ukažte, že je-li \(L\) jazyk z třídy \(\mathrm{NP}\), pak \(L^*\) také patří do \(\mathrm{NP}\).
  3. Ukažte, že je-li \(L\) jazyk z třídy \(\mathrm{P}\), pak \(L^*\) také patří do \(\mathrm{P}\).

Domácí úkoly k 4. cvičení

  1. Rozhodněte, zda mezi následujícími dvojicemi tříd existuje nějaký vztah (ostrá nebo neostrá inkluze), případně zda není možno žádný vztah mezi nimi pomocí nám známých prostředků ukázat. Každá dvojice je za 1 bod.
    1. $\mathrm{TIME}(2^n)$$\mathrm{NSPACE}(\sqrt{n})$
    2. $\mathrm{NSPACE}((\log n)^3)$ $\mathrm{SPACE}(n)$
    3. $\mathrm{NTIME}(n^3)$ $\mathrm{SPACE}(n^6)$

5. cvičení

  1. Definujme problémy Klika, Nezávislá množina a Vrcholové pokrytí následovně:
    Klika
    Instance: Graf $G=(V, E)$ a přirozené číslo $k\geq 0$.
    Otázka: Obsahuje $G$ jako podgraf úplný graf (kliku) s alespoň $k$ vrcholy?
    Nezávislá množina
    Instance: Graf $G=(V, E)$ a přirozené číslo $k$.
    Otázka: Existuje v grafu $G$ nezávislá množina velikosti alespoň $k$? Tj. existuje množina vrcholů $S\subseteq V$, pro kterou platí, že $|S|\geq k$ a žádné dva vrcholy v $S$ nejsou spojeny hranou?
    Vrcholové pokrytí
    Instance:Graf $G=(V,E)$ a přirozené číslo $k\geq 0$.
    Otázka:Existuje množina vrcholů $S\subseteq V$ velikosti nejvýš $k$, která obsahuje alespoň jeden vrchol z každé hrany (tj. pokrývá hrany $G$)?
    Ukažte, že tyto problémy jsou na sebe vzájemně polynomiálně převoditelné.
  2. Uvažte následující dva problémy:
    Celočíselné programování
    Instance: Matice nad celými čísly $A$ typu $m\times n$ a vektor celých čísel $b$ délky $m$.
    Otázka: Existuje celočíselný vektor $x$ délky $n$, pro který platí $Ax\geq b$?
    Binární celočíselné programování
    Instance: Matice nad celými čísly $A$ typu $m\times n$ a vektor celých čísel $b$ délky $m$.
    Otázka: Existuje vektor $x\in\{0,1\}^n$, pro který platí $Ax\geq b$?
    Ukažte, že oba problémy jsou NP-těžké (převodem z Kliky, Nezávislé množiny nebo Vrcholového pokrytí. Ukažte, že problém Binárního celočíselného programování patří do NP a je tedy NP-úplný. Rozmyslete si, proč není tak snadné zdůvodnit, že i problém celočíselného programování bez omezení hodnot patří do třídy NP (byť to platí).
  3. Definujme problém Hamiltonovská kružnice následovně:
    Hamiltonovská kružnice (HK)
    Instance: Neorientovaný graf $G=(V, E)$.
    Otázka: Existuje v grafu $G$ hamiltonovská kružnice, tj. kružnice procházející všemi vrcholy?
    O tomto problému je známo, že je NP-úplný. Ukažte s pomocí problému Hamiltonovské kružnice, že následující problémy jsou NP-úplné:
    Orientovaná Hamiltonovská kružnice (OHK)
    Instance: Orientovaný graf $G=(V, E)$.
    Otázka: Existuje v grafu $G$ hamiltonovská kružnice, tj. kružnice procházející všemi vrcholy?
    Hamiltonovská cesta z $s$ do $t$ (HC($s$, $t$))
    Instance: Neorientovaný graf $G=(V, E)$ a vrcholy $s$ a $t$.
    Otázka: Existuje v grafu $G$ hamiltonovská cesta z vrcholu $s$ do vrcholu $t$? Tj. existuje v grafu $G$ cesta z vrcholu $s$ do $t$, která prochází každým vrcholem grafu $G$ právě jednou?
    Hamiltonovská cesta (HC)
    Instance: Neorientovaný graf $G=(V, E)$.
    Otázka: Existuje v grafu $G$ hamiltonovská cesta? Tj. existuje v grafu $G$ cesta, která prochází každým vrcholem grafu $G$ právě jednou?
  4. Ukažte, že následující problém je NP-úplný:
    Pokrytí orientovaných cyklů
    Instance: Orientovaný graf $G=(V, E)$ a přirozené číslo $k$.
    Otázka: Existuje množina vrcholů $S\subseteq V$ velikosti nejvýš $k$, která obsahuje alespoň jeden vrchol z každého orientovaného cyklu v $G$?

Domácí úkoly k 5. cvičení

  1. Problém Loupežníci definujeme následujícím způsobem:
    Loupežníci
    Instance: Množina prvků $A$ a s~každým prvkem $a\in A$ asociovaná cena (váha, velikost, \dots) $s(a)\in\mathbb{N}$.
    Otázka: Lze rozdělit prvky z~$A$ na dvě poloviny s~toutéž celkovou cenou? Přesněji, existuje množina $A'\subseteq A$ taková, že $$\sum_{a\in A'}s(a)=\sum_{a\in A\setminus A'}s(a)\;?$$
    Ukažte, že problém Loupežníci je polynomiálně převoditelný na problémy Batoh a Rozvrhování. [2 body]:
    Batoh
    Instance: Množina předmětů $A$, pro každý předmět $a$ přirozené číslo $s$($a$) udávající jeho velikost a přirozené číslo $v$($a$) udávající jeho cenu, přirozená čísla $B$ a $K$.
    Otázka: Existuje množina předmětů $A'$, pro kterou platí, že $\sum_{a\in A'}s(a)\leq B$ a $\sum_{a\in A'}v(a)\geq K$?
    Rozvrhování
    Instance: Počet procesorů $m$, množina úloh $U$, pro každou úlohu $u$ přirozené číslo $d(u)$ a přirozené číslo $D$.
    Otázka: Existuje rozdělení množiny předmětů $U$ na $m$ po dvou disjunktních podmnožin $U_1, \dots, U_m$ tak, aby pro každou z nich, tedy pro každé $1\leq i\leq m$ platilo, že $\sum_{u\in U_i}d(u)\leq D$?
  2. Ukažte, že následující problém je NP-úplný (k důkazu těžkosti využijte některý z problémů, jež jsme zmiňovali na přednášce nebo na cvičení) [1 bod]:
    Množinové pokrytí
    Instance: Množina prvků $U$, systém množin těchto prvků $\mathcal{S}=\{S_i\;|\;S_i\subseteq U, i=1, \ldots, m\}$ a přirozené číslo $k$.
    Otázka: Existuje výběr nejvýš \(k\) množin z $\mathcal{S}$, které dohromady pokrývají všechny prvky z U? Přesněji, existuje množina indexů $I\subseteq\{1, \ldots, m\}$, pro kterou platí, že $|I|\leq k$ a $U=\bigcup_{i\in I}S_i$?