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

Petr Kučera, KTIML MFF UK

Zimní semestr 2015/2016

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

Odkazy a dokumenty

Zkouška

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 čtvrtečním cvičením, podmínky udělení zápočtu na pondělní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í.

Bylo zadáno 6 domácích úkolů, k získání zápočtu je proto třeba nasbírat 12 bodů.

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

1. přednáška (7. října 2015)

Slajdy 1—33. Motivační příklad. Definice Turingových strojů a příklad Turingova stroje rozpoznávajícího jazyk $L=\{0^n1^n\;|;n\geq 0\}$. Rozhodnutelné (=rekurzivní) a částečně rozhodnutelné (=rekurzivně spočetné) jazyky a jejich základní vlastnosti. Postova věta.

2. přednáška (14. října 2015)

Slajdy 34-50. Turingovsky vyčíslitelné funkce. Kódování Turingových strojů a Gödelovo číslo. Nerozhodnutelnost diagonalizačního jazyka. Univerzální Turingův stroj a vlastnosti univerzálního jazyka. Problém zastavení.

3. přednáška (21. října 2015)

Slajdy 51-61. RAM a ekvivalence s Turingovými stroji.

4. přednáška (4. listopadu 2015)

Slajdy 63—70. Turingovsky vyčíslitelné funkce. Vyčíslitelnost (částečně) rozhodnutelných jazyků. $m$-převoditelnost a úplnost. $m$-úplnost problému zastavení a jeho diagonály.

5. přednáška (11. listopadu 2015)

Slajdy 71—73. Riceova věta. Postův korespondenční problém.

6. přednáška (18. listopadu 2015)

Slajdy 74—90. 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ého lematu).

7. přednáška (25. listopadu 2015)

Slajdy 90—92. Savičova věta. Věta o deterministické prostorové hierarchii.

8. přednáška (2. prosince 2015)

Slajdy 93—98. Deterministická prostorová hierarchie. Věta o deterministické časové hierarchii a deterministická časová hierarchie. Definice polynomiální převoditelnosti a NP-úplnosti. Důkaz, že problém Kachlíkování je NP-úplný.

9. přednáška (9. prosince 2015)

Slajdy 99—109. Důkazy NP-úplnosti Splnitelnosti, 3-Splnitelnosti a Vrcholového pokrytí. Seznam dalších NP-úplných problémů (bez důkazu NP-úplnosti).

10. přednáška (16. prosince 2015)

Slajdy 110—125. Optimalizační problémy a aproximační algoritmy. Aproximační algoritmus pro Bin Packing. Neaproximovatelnost Obchodního cestujícího. Pseudopolynomiální algoritmus pro Batoh. Pseudopolynomiální algoritmy a silná NP-úplnost. Silná NP-úplnost Obchodního cestujícího.

11. přednáška (13. ledna 2016)

Slajdy 126—143. Aproximační schéma pro Batoh. Aproximační schémata a silná NP-úplnost. Třídy co-NP a #P.

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\}$.
  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. Předpokládejte, že Turingův stroj s poloviční páskou má na prvním políčku zvláštní znak zarážky (▷).
  3. Popište, jak lze převést Turingův stroj s dvěma (nebo více) páskami na jednopáskový Turingův stroj.
  4. 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).
  5. 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.
  6. 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.
  7. 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.
  8. Ukažte, že jsou-li $L_1$ a $L_2$ (částečně) rozhodnutelné jazyky, pak i jazyk $L=L_1\cdot L_2=\{w_1w_2\;|\;w_1\in L_1\wedge w_2\in L_2\}$ je (částečně) rozhodnutelný.

Domácí úkoly k 1. cvičení (zadání 8. října 2015, odevzdání do začátku cvičení 22. října 2015; shodné zadání 15. října 2015, odevzdání do začátku cvičení 29. října 2015)

  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. Ukažte, že je-li $L$ částečně rozhodnutelný jazyk, pak i jazyk $L^*=\{w\;|\;(\exists k\in{\mathbb N})(\exists u_1, \dots, u_k\in L)[w=u_1u_2...u_k]\}$ je částečně rozhodnutelný. Při řešení mějte na paměti, že pokud $L=L(M)$ pro nějaký TS $M$, pak se může stát, že $M(w)$ se nezastaví pro $w\not\in L$.
  3. [2 body]

2. cvičení

  1. Ukažte, že jazyk $L=\{w_i\;|\;w_{2i}\not\in L(M_i)\}$ není částečně rozhodnutelný.
  2. Ukažte, že jazyk $L$ je částečně rozhodnutelný, právě když existuje Turingův stroj $M$, pro který platí, že $L=\{x\;|\;M(x)\!\downarrow\}$.
  3. Ukažte, že jazyk $K=\{w_i\;|\;M_i(w_i)\!\downarrow\}$ je částečně rozhodnutelný, ale není rozhodnutelný (jde o diagonálu problému zastavení).
  4. Popište způsob kódování dvojic řetězců pomocí jednoho řetězce. Tj. popište prostou algoritmicky vyčíslitelnou funkci $f:\Sigma^*\times\Sigma^*\mapsto\Sigma^*$, kterou lze navíc algoritmicky invertovat. (Řetězec kódující dvojici $x$ a $y$ budeme označovat pomocí $\langle x, y\rangle$.)
  5. Ukažte, že jazyk $K_0=\{\langle w_i, x\rangle\;|\;M_i(x)\!\downarrow\}$ (problém zastavení) je částečně rozhodnutelný, ale není rozhodnutelný.
  6. Ukažte, že jazyk $K_1=\{w_i\;|\;(\exists y)[M_i(y)\!\downarrow]\}$ je částečně rozhodnutelný.
  7. Ukažte, že jazyk $L$ je částečně rozhodnutelný, právě když existuje rozhodnutelný jazyk $B$, pro který platí, že $L=\{x\;|\;(\exists y)[\langle x, y\rangle\in B\}$.

Domácí úkoly k 2. cvičení (zadání 22. října 2015, odevzdání do začátku cvičení 5. listopadu 2015, zadání 29. října 2015, odevzdání do začátku cvičení 12. listopadu 2015).

  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. 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í. [1 bod]

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=\{w_{2i}\;|\;w_i\in A\}\cup\{w_{2i+1}\;|\;w_i\in B\} .\] To je při našem číslování řetězců ekvivalentní definici \[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. Ukažte, že $K\leq_mK_1$ a množina $K_1$ je tedy $m$-úplná.
  5. Ukažte, že $K\leq_mInf$ a $K\leq_mFin$, kde \[\begin{eqnarray*} Inf&=&\{w_i\;|\;\mbox{dom }\varphi_i\mbox{ je nekonečná}\}\\ Fin=\overline{Inf}&=&\{w_i\;|\;\mbox{dom }\varphi_i\mbox{ je konečná}\}\\ \end{eqnarray*}\] (zde $\mbox{dom }\varphi_i=\{y\;|\;\varphi_i(y)\downarrow\}=\{y\;|\;M_i(y)\downarrow\}$)
  6. Problém Použití stavu definujeme následovně:
    Použití stavu
    Instance: Turingův stroj $M$ a číslo $k$ stavu $q_k$.
    Otázka: Existuje vstup $x$ takový, že $M$ při práci nad vstupem $x$ použije stav $q_k$?
    Zformulujte problém Použití stavu jako jazyk a ukažte, že je částečně rozhodnutelný.

Domácí úkoly k 3. cvičení (zadání 5. listopadu 2015, odevzdání do začátku cvičení 19. listopadu 2015, zadání 12. listopadu 2015, odevzdání do začátku cvičení 26. listopadu 2015)

  1. Ukažte, že problém Použití stavu je algoritmicky nerozhodnutelný. (Například tím, že na něj převedete problém zastavení.) [2 body]
  2. 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]

4. cvičení

  1. Ukažte, že následující jazyk $L=\{w_e\;|\;(\forall x)[x\in L(M_e)\Leftrightarrow x^R\in L(M_e)]\}$ není rozhodnutelný.
  2. Rozhodněte, zda jazyk $S=\{\langle w_x, w_y, w_z\rangle\;|\;w_x\in L(M_x)\cup L(M_y)\}$ je rozhodnutelný, nebo alespoň částečně rozhodnutelný.
  3. Rozhodněte, zda jazyk $S'=\{\langle w_x, w_y\rangle\;|\; L(M_x)\cap L(M_y)=\emptyset\}$ je rozhodnutelný, nebo alespoň částečně rozhodnutelný.
  4. Uvažme problém, v němž vstupem je TS $M$ a ptáme se, zda $L(M)$ patří do třídy $P$, ukažte, že tento problém není rozhodnutelný.
  5. Uvažme problém, v němž vstupem je TS $M$ a ptáme se, zda pracuje v čase $O(n^2)$, ukažte, že tento problém není algoritmicky řešitelný. (Tento důkaz jsem ukazoval na sudém cvičení.)

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

  1. Rozhodněte, zda jazyk $S=\{w_e\;|\;|L(M_e)|\leq 10\}$ je rozhodnutelný. Pokud není rozhodnutelný, rozhodněte, zda $S$ nebo $\overline{S}$ je částečně rozhodnutelný jazyk. [3 body]

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)$ a vrcholy $s$ a $t$.
    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. Ukažte, že problém Hamiltonovské kružnice lze polynomiálně převést na problém Obchodního cestujícího, který je definován níže. [1 bod]
    Obchodní cestující (OC)
    Instance: $n$ měst $a_1, \dots, a_n$ a funkce určující vzdálenost mezi každými dvěma městy $d(a_i,a_j)\geq 0$, číslo $D\geq 0$.
    Otázka: Existuje pořadí (permutace) měst, při němž obchodní cestující objede všechna města, vrátí se do počátečního a najezdí přitom vzdálenost nejvýš $D$? Tj. existuje permutace $\pi:\{1, \dots, n\}\mapsto\{1, \dots, n\}$ taková, že
    $\big(\sum_{i=1}^{n-1}d(a_{\pi(i)},a_{\pi(i+1)})\big)+d(a_{\pi(n)},a_{\pi(1)})\leq D$?
  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, \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$?

6. cvičení

  1. 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$.
  2. Definujme optimalizační úlohu Obchodního cestujícího s trojúhelníkovou nerovností následovně:
    Obchodní cestující s trojúhelníkovou nerovností ($\triangle$-OC)
    Instance: $n$ měst $C=\{c_1, \dots, c_n\}$ a funkce určující vzdálenost mezi každými dvěma městy $d(c_i,c_j)\geq 0$. Předpokládáme, že $d$ splňuje trojúhelníkovou nerovnost, tj. pro každá tři města $c_i, c_j, c_k$ platí $d(c_i, c_j)+d(c_j, c_k)\geq d(c_i, c_k)$.
    Cíl: Najít pořadí (permutace) měst, při němž obchodní cestující objede všechna města, vrátí se do počátečního a najezdí přitom co nejmenší vzdálenost? Tj. cílem je najít permutaci $\pi:\{1, \dots, n\}\mapsto\{1, \dots, n\}$, pro kterou je \[\big(\sum_{i=1}^{n-1}d(c_{\pi(i)},c_{\pi(i+1)})\big)+d(c_{\pi(n)},c_{\pi(1)})\] je minimální.
    1. Ukažte, že je-li $T$ minimální kostra úplného grafu daném městy a vzdálenostmi mezi nimi, tak platí $\Vert T\Vert\leq opt(C, d)$. (Pomocí $\Vert T\Vert$ označujeme velikost minimální kostry.)
    2. Popište na základě tohoto pozorování aproximační algoritmus s aproximačním poměrem 2 pro $\triangle$-OC.
    3. Nechť $T$ je minimální kostra úplného grafu daném městy a vzdálenostmi mezi nimi v instanci $\triangle$-OC a nechť $M$ je perfektní párování minimální ceny na vrcholech s lichými stupni v $T$. Ukažte, že $\Vert M\Vert\leq\frac{1}{2}opt(C, d)$. Popište s pomocí tohoto pozorování aproximační algoritmus s aproximačním faktorem $\frac{3}{2}$ pro $\triangle$-OC.
  3. 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í.
  4. 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ů.
  5. 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]$?
    4. $(\forall v)\;[\varphi(v)=0]$?
  6. Popište polynomiální algoritmus pro 2SAT, který nalezne splňující ohodnocení k zadané formuli v 2KNF. Formule 2KNF obsahuje klauzule délky nejvýš 2, tedy s nejvýš dvěma literály.

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

  1. 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 [1,5 bodu]:
    MaxSat
    Instance:Formule $\varphi$ v KNF.
    Cíl:Najít ohodnocení proměnných $v$, které maximalizuje počet splněných klauzulí.
  2. O formuli $\varphi$ v KNF řekneme, že je hornovská, pokud každá klauzule $\varphi$ obsahuje nejvýš jeden pozitivní literál. Ukažte, že problém HornSat, v němž se ptáme, zda daná hornovská formule je splnitelná, je polynomiálně řešitelný. [1,5 bodu]