NTIN090 - Základy složitosti a vyčíslitelnosti

Petr Kučera, KTIML MFF UK

English version

Zimní semestr 2019/2020

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í

Přednáška a cvičení v lednu odpadají, přesněji...

Přednáška 8. ledna odpadá!

Cvičení 9. ledna odpadá!

Odkazy a dokumenty

Reklama

Petr Savický z Ústavu informatiky Akademie věd nabízíme výzkumnou pozici pro studenty. Pozice je zaměřena na využití SAT solverů, nicméně nepředpokládají se žádné předběžné znalosti z této oblasti. Znalost programovacího jazyka C++ nebo Python zcela postačuje. V případě dosažení zajímavých výsledků je možné je použít jako základ bakalářské či diplomové práce. Více též na plakátku. V případě zájmu či dotazů mne můžete kontaktovat.

Zkouška

Ráno (obvykle) v 9:30 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. 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 dostanete dvě otázky ze seznamu otázek. Půjde buď o jednu otázku ze skupiny A a jednu ze skupiny D, nebo jednu otázku ze skupiny B a jednu otázku ze skupiny C.

Klasifikace bude určena na základě písemné i ústní části.

Zápočty

Následující informace se vztahují pouze k mým čtvrtečním cvičením. Úterní cvičení vede Vladan Majerech.

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í.

Bylo zadáno 5 sad úkolů, na zápočet je tedy potřeba 10 bodů.

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

1. přednáška (2. října 2019)

Slajdy 1-38. Motivační příklad. Definice Turingova stroje, varianty TS.

2. přednáška (9. října 2019)

Slajdy 39-60. Převod \(k\)-páskového Turingova stroje na jednopáskový. RAM a jeho ekvivalence s Turingovými stroji. Kódování a číslování Turingových strojů.

3. přednáška (16. října 2019)

Slajdy 61-78. Gödelovo číslo. Univerzální Turingův stroj. Základní vlastnosti rozhodnutelných a částečně rozhodnutelných jazyků, Postova věta. Diagonalizační jazyk není částečně rozhodnutelný. Jazyk univerzálního Turingova stroje a problém zastavení jsou částečně rozhodnutelné, nikoli však rozhodnutelné. Algoritmicky vyčíslitelné funkce.

4. přednáška (23. října 2019)

Slajdy 79-86. Ekvivalentní definice částečně rozhodnutelných a rozhodnutelných jazyků. Výčet prvků jazyka (enumerace). Definice \(m\)-převoditelnosti, \(m\)-úplnosti a jejich základní vlastnosti.

5. přednáška (30. října 2019)

Slajdy 87-90. \(m\)-úplnost diagonály problému zastavení. Riceova věta. Postův korespondenční problém.

6. přednáška (6. listopadu 2019)

Slajdy 92-110. Základní třídy složitosti. Definice tříd P, PSPACE, EXPTIME. Definice třídy NP pomocí verifikátorů. Nedeterministické Turingovy stroje a základní nedeterministické třídy složitosti. Ekvivalentní definice třídy NP pomocí nedeterministických Turingových strojů s důkazem ekvivalence. Věta o vztazích mezi třídami (důkaz bude ukázán příště) a její využití pro důkaz vztahů mezi třídami.

7. přednáška (13. listopadu 2019)

Slajdy 109, 111-112. Věta o vztazích mezi třídami (důkaz). Savičova věta.

8. přednáška (20. listopadu 2019)

Slajdy 113-117. Věty o hierarchiích.

9. přednáška (27. listopadu 2019)

Slajdy 118-122. Polynomiální převoditelnost. NP-úplnost. NP-úplnost Kachlíkování a Splnitelnosti (Cookova-Levinova věta).

10. přednáška (4. prosince 2019)

Slajdy 123-142. NP-úplnost problémů 3-Splnitelnost a Loupežníci. Problémy Vrcholového pokrytí a Trojrozměrného párování a Hamiltonovské kružnice zmíněny bez důkazu. Pseudopolynomiální algoritmus pro Batoh. Pseudopolynomiální algoritmy a silná NP-úplnost. Silná NP-úplnost Obchodního cestujícího.

11. přednáška (11. prosince 2019)

Slajdy 143-157. Aproximační algoritmy, definice a příklad aproximačního algoritmu pro Bin Packing. Zmíněn (bez důkazu) aproximační algoritmus pro Množinové pokrytí. Těžkost aproximace Obchodního cestujícího. Úplně polynomiální aproximační schéma pro Batoh. Aproximační schémata - definice. Souvislost úplně polynomiálních aproximačních schémat se silnou NP-úplností.

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. (Jen sudé cvičení) 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.

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

Jsou shodné pro liché i sudé 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. (Liché cvičení) 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.
  2. 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.
  3. Ukažte, že je-li \(A\) částečně rozhodnutelný jazyk, pak jazyk \[L=\{x\mid(\exists y)[\langle x, y\rangle\in A]\}\] je též částečně rozhodnutelný.
  4. Ukažte, že jazyk $L$ je částečně rozhodnutelný, právě když existuje rozhodnutelný jazyk $A$, pro který platí, že \[L=\{x\mid(\exists y)[\langle x, y\rangle\in A]\}\]
  5. 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]\}$
  6. (Sudé cvičení) Ukažte, že jsou-li $A$ a $B$ dva netriviální (tj. $A, B\neq\emptyset,\Sigma^*$) rozhodnutelné jazyky, pak $A\leq_mB$.
  7. (Sudé cvičení) Ukažte, že je-li $A$ částečně rozhodnutelný jazyk a $A\leq_m\overline{A}$, pak $A$ je ve skutečnosti rozhodnutelný jazyk.
  8. (Sudé cvičení) Operaci disjunktního sjednocení $\oplus$ jazyků $A$ a $B$ nad abecedou \(\{0, 1\}\) 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 nad abecedou \(\{0, 1\}\), pro který platí, že $A\leq_m C$ i $B\leq_m C$, pak rovněž $A\oplus B\leq_m C$.
  9. (Sudé cvičení) Uvažme jazyk $J=L_u\oplus \overline{L_u}$. Ukažte, že $J$ ani $\overline{J}$ nejsou částečně rozhodnutelné jazyky.
  10. (Sudé cvičení) Ukažte, \(J\leq_m\overline{J}\).

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

  1. Ukažte, že následující jazyk je částečně rozhodnutelný, ale není rozhodnutelný. [1 bod] \[ \operatorname{PSE-x}=\{\langle M, q, x\rangle\;|\;\text{$M$ použije při výpočtu nad $x$ stav $q$}\}\] Pro nerozhodnutelnost si rozmyslete, jak by pomocí \(\operatorname{PSE-x}\) bylo možno rozhodnout například univerzální jazyk.
  2. Ukažte, že následující jazyky jsou částečně rozhodnutelné [každá za 1 bod]: \begin{align*} \mathrm{HASPRIME}&=\{\langle M\rangle\mid (\exists p)[\text{\(p\) je prvočíslo a \(\langle p\rangle\in L(M)\)}]\}\\ \mathrm{PSE}&=\{\langle M, q\rangle\;|\;(\exists x)[\text{$M$ použije při výpočtu nad $x$ stav $q$}]\}\\ \end{align*}

3. cvičení

  1. (Liché cvičení) Ukažte, že je-li $A$ částečně rozhodnutelný jazyk a $A\leq_m\overline{A}$, pak $A$ je ve skutečnosti rozhodnutelný jazyk.
  2. (Liché cvičení) Operaci disjunktního sjednocení $\oplus$ jazyků $A$ a $B$ nad abecedou \(\{0, 1\}\) 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 nad abecedou \(\{0, 1\}\), pro který platí, že $A\leq_m C$ i $B\leq_m C$, pak rovněž $A\oplus B\leq_m C$.
  3. (Liché cvičení) Uvažme jazyk $J=L_u\oplus \overline{L_u}$. Ukažte, že $J$ ani $\overline{J}$ nejsou částečně rozhodnutelné jazyky.
  4. (Liché cvičení) Ukažte, \(J\leq_m\overline{J}\).
  5. Uvažme následující jazyk: $$ EQ=\{\langle M, N\rangle\mid L(M)=L(N)\}\text{.} $$
    1. Ukažte, že \(L_u\leq_m EQ\).
    2. Ukažte, že \(L_u\leq_m \overline{EQ}\).
  6. (Sudé cvičení) Ukažte, že univerzální jazyk \(L_u\) je \(m\)-převoditelný na jazyky \(\mathrm{Fin}\) a \(\mathrm{Inf}\), kde \begin{eqnarray*} \mathrm{Fin}&=&\{\langle M\rangle\;|\;L(M)\text{ je konečný jazyk}\}\\ \mathrm{Inf}=\overline{\mathrm{Fin}}&=&\{\langle M\rangle\;|\;L(M)\text{ je nekonečný jazyk}\}\\ \end{eqnarray*}
  7. 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é. (Převodem z \(\mathrm{HALT}=\{\langle M, x\rangle\mid M(x)\;\downarrow\}\)).
    2. Ukažte, že \(PPV\) ani jeho doplněk nejsou není částečně rozhodnutelné (převodem z \(\overline{\mathrm{HALT}}\)).

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

  1. 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]
  2. Uvažme jazyk $$S=\left\{\langle M\rangle\;|\;(\forall x\in\Sigma^*)\left[x\in L(M)\Leftrightarrow x^R\in L(M)\right]\right\}\text{.}$$ Ukažte, že \(L_u\leq_m S\) a současně \(L_u\leq_m\overline{S}\). Pomocí \(x^R\) označujeme zrcadlové otočení řetězce \(x\), tj. řetězec \(x\) napsaný pozpátku. [2 body]

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 \log n)\)\(\mathrm{TIME}(2^{(n^2)})\)
    2. \(\mathrm{TIME}(2^{(n^2)})\)\(\mathrm{TIME}(2^{n \log n})\)
    3. \(\mathrm{TIME}(2^{n \log n})\)\(\mathrm{NSPACE}(\log^2 n)\)
    4. \(\mathrm{NSPACE}(\log^2 n)\)\(\mathrm{NTIME}(n)\)
    5. \(\mathrm{NTIME}(n)\)\(\mathrm{SPACE}(n \log n)\)
    6. \(\mathrm{SPACE}(n \log n)\)\(\mathrm{TIME}(2^{n \log n})\)
    7. \(\mathrm{TIME}(2^{(n^2)})\)\(\mathrm{NSPACE}(\log^2 n)\)
    8. \(\mathrm{TIME}(2^{n \log n})\)\(\mathrm{NTIME}(n)\)
    9. \(\mathrm{NSPACE}(\log^2 n)\)\(\mathrm{SPACE}(n \log n)\)
    10.\(\mathrm{NTIME}(n)\)\(\mathrm{TIME}(2^{(n^2)})\)

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)$

Cvičení 28. listopadu proběhne výjimečně v místnosti S10.

5. cvičení (zatím jen liché)

  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. Ukažte, že problém Dominující množiny je NP-úplný (převodem z problému Vrcholového pokrytí).
    Dominující množina
    Instance:Graf $G=(V, E)$ a přirozené číslo $k$.
    Otázka:Existuje v \(G\) množina vrcholů $S\subseteq V$ velikosti nejvýš \(k\), pro kterou platí, že každý vrchol \(v\in V\) má souseda v \(S\)?
  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. 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 ze Splnitelnosti, 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í).

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

  1. Ukažte, že následující problém je NP-úplný (převodem z problému Vrcholového pokrytí, nezapomeňte zdůvodnit, že tento problém patří do NP) [1 bod].
    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$?
  2. 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, …) $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$?

6. cvičení

  1. Předpokládejme, že rozhodovací verzi problému Obchodního cestujícího umíme rozhodnout v polynomiálním čase. To znamená, že máme funkci rozhodniOC(C, d, D), kde \(C\) je množina měst, \(d\) určuje vzdálenosti mezi nimi a \(D\) je limit na vzdálenost a která rozhodne, zda existuje pořadí měst, při němž navštíví obchodní cestující všechna města, vrátí se do svého domovského města a nacestuje přitom vzdálenost nejvýš \(D\). Popište, jak za tohoto předpokladu vyřešit v polynomiálním čase optimalizační verzi Obchodního cestujícího, tedy popište algoritmus, který nalezne pořadí měst, při němž nacestuje obchodní cestují najkratší vzdálenost. Algoritmus bude pracovat v polynomiálním čase za předpokladu, že volání funkce rozhodniOC(C, d, D) proběhne v konstantním čase.
  2. Ukažte, že pro každé $m$ existuje formule $\varphi$ v KNF s $m$ klauzulemi taková, že libovolná formule $\psi$ v DNF, která je ekvivalentní s $\varphi$, obsahuje alespoň $2^m$ termů.
  3. Předveden převod obecné formule \(\varphi\) na KNF \(\psi\), pro kterou platí, že \(\varphi\) je splnitelná právě když \(\psi\) je splnitelná.
  4. Rozmyslete si, jak obtížné je o dané formuli $\varphi$ zodpovědět následující otázky v závislosti na tom, je-li $\varphi$ KNF, DNF, či formule v nijak neomezovaném tvaru.
    1. $(\exists v)\;[\varphi(v)=1]$?
    2. $(\exists v)\;[\varphi(v)=0]$?
    3. $(\forall v)\;[\varphi(v)=1]$? (jen letmo zmíněno)
    4. $(\forall v)\;[\varphi(v)=0]$? (jen letmo zmíněno)
  5. Definujme optimalizační úlohu Vrcholového pokrytí následovně:
    Vrcholové pokrytí
    Instance:Neorientovaný graf $G=(V,E)$
    Cíl:Nalézt co nejmenší vrcholové pokrytí grafu $G$. Tj. cílem je nalézt množinu $S\subseteq V$ s co nejmenším počtem vrcholů, pro kterou by platilo, že $(\forall\{u,v\}\in E)\;[\{u,v\}\cap S\neq\emptyset]$.
    Uvažme nyní následující jednoduchý aproximační algoritmus pro úlohu Vrcholového pokrytí:
    1. $S:=\emptyset$
    2. Dokud je $E\neq\emptyset$
      1. Vyber libovolnou hranu $\{u,v\}\in E$
      2. $S=S\cup\{u,v\}$
      3. Odstraň z $E$ všechny hrany, které jsou incidentní s $u$ nebo $v$.
    3. Vrať $S$.
    Ukažte, že $S\leq 2OPT(G)$, kde $OPT(G)$ označuje velikost nejmenšího vrcholového pokrytí grafu $G$.

Dodatečné domácí úkoly

  1. Předpokládejte, že máte k dispozici funkci/černou skříňku $sat(\varphi)$, která pro danou formuli $\varphi$ v KNF odpoví, zda je $\varphi$ splnitelná, či nikoli. Odpověď vrací jako booleovskou hodnotu. Popište algoritmus, který nalezne splňující ohodnocení pro danou formuli $\varphi$ v KNF. Algoritmus může volat černou skříňku $sat()$, přičemž požadujeme, aby algoritmus pracoval v polynomiálním čase, považujeme-li čas volání funkce $sat()$ za konstantní. [2 body]
  2. Ukažte, že pro každou formuli $\varphi$ v KNF existuje ohodnocení $v$, které splňuje nejméně polovinu klauzulí. Popište na základě toho 2-aproximační algoritmus pro úlohu MaxSat [2 boy]:
    MaxSat
    Instance:Formule $\varphi$ v KNF.
    Cíl:Najít ohodnocení proměnných $v$, které maximalizuje počet splněných klauzulí.
  3. Ukažte, že problém Dvojité splnitelnosti je NP-úplný. Každá klauzule by měla obsahovat každou proměnnou nejvýš jednou. [2 body]
    Dvojitá splnitelnost
    Instance:Formule \(\varphi\) v KNF.
    Otázka:Existují dvě různá splňující ohodnocení \(\varphi\)? Přesněji, existují dvě různá ohodnocení proměnných \(u\) a \(v\), pro která platí \(\varphi(u)=1\) i \(\varphi(v)=1\).
  4. Uvažte následující dva jazyky \begin{eqnarray} S_1&=&\{\langle M\rangle\;|\;(\exists x\in\Sigma^*)[M(x)\!\downarrow\text{ a po ukončení výpočtu \(M\) nad \(x\) obsahuje páska právě jen slovo \(x\), tj. vypadá stejně jako na začátku (v průběhu výpočtu ovšem může \(M\) využívat pásku libovolně)}] \}\\ S_2&=&\{\langle M, N\rangle\;|\;L(M)\setminus L(N)\neq\emptyset\} \end{eqnarray} Rozhodněte (a ukažte), zda \(S_1\) nebo \(S_2\) jsou rozhodnutelné jazyky. Pokud usoudíte, že \(S_1\) (nebo \(S_2\)) není rozhodnutelný, rozhodněte (a ukažte), zda \(S_1\) (resp. \(S_2\)) nebo jeho doplněk je částečně rozhodnutelný. [Každý jazyk je za 1,5 bodu.]
Petr Kučera <>