:: Literál je buď proměnná nebo její negace. :: **Pozitivní literál** je každá proměnná $x$ . :: **Negativní literál** je každá negace proměnnej $\overline x$. :: **Klauzule** je disjunkcí literálů, která neobsahuje dva literály s touž proměnnou $x ∨ \overline y ∨ \overline z$. :: Formule $φ$ je v **konjunktivně normální formě (KNF)**, pokud je konjunkcí klauzulí $(x ∨ y) ∧ \overline z$. :: Je-li $φ$ formulí na n proměnných a $t ∈ \{0, 1\}^n$ , pak $φ(t)$ značí hodnotu $φ$ v **ohodnocení** $t$. **Splnitelnost formule v KNF (SAT)** * **Instance:** Formule $φ$ na $n$ proměnných v KNF * **Otázka:** **∃** ohodnocení, pro které je $φ$ splněná? Důkaz transformací **KACHL ∝ SAT**: pomocí proměnných $x_{ijk}$, kde $x_{ijk} = 1$, pokud na pozici $[i,j]$ se nachází kachlík typu $k$. Jednotlivé klauzule se vytvoří tak, aby zaručovaly, že na každé pozici je právě jeden kachlík, že kachlíky navazují horizontálně, vertikálně i na kraje stěny. {{theorem | SAT je NP-úplný problém | NP-úplnost SAT }} Dk (KACHL → SAT - myšlenka) :: :: pomocí proměnných $x_{ijk}$, kde $x_{ijk} = 1$, pokud na pozici $[i,j]$ se nachází kachlík typu $k$. Jednotlivé klauzule se vytvoří tak, aby zaručovaly, že na každé pozici je právě jeden kachlík, že kachlíky navazují horizontálně, vertikálně i na kraje stěny. Dk (KACHL → SAT) :: To, že $SAT$ patří do NP, plyne z toho, že pokud dostaneme vektor $t ∈ {0, 1}^n$, můžeme spočítat hodnotu φ(t) v polynomiálním čase. Certifikátem kladné odpovědi je tedy splňující ohodnocení. Toto ohodnocení je ve skutečnosti řešením úlohy splnitelnosti, v níž chceme splňující ohodnocení nalézt a ne jen zjistit, zda existuje, tato úloha tedy patří do NPF. $NP$-těžkost splnitelnosti ukážeme převodem z problému Kachlíkování. Uvažme instanci Kachlíkování danou množinou barev $B$, přirozeným číslem $s$, čtvercovou sítí $S$ velikosti $s × s$, jejíž okraje jsou obarveny barvami z $B$, a množinou typů kachlíků $K = \{T1, . . . , T|K|\}$. Popíšeme, jak zkonstruovat formuli $φ$ v KNF, která bude splnitelná právě tehdy, když tato instance má přípustné vykachlíkování. Formule $φ$ bude využívat $\{ s . |K| \}$ proměnných $x_{i,j,k}$ pro $\{ i, j = 1, . . . , s, \}$ a $\{ k = 1, . . . , |K| \}$. Konstrukcí formule $φ$ zabezpečíme, že ve splňujícím ohodnocení bude hodnota $xi, j, k = 1$ odpovídat tomu, že na políčko $S[i, j]$ umístíme kachlík Tk. V konstrukci použijeme následující dvě množiny určující nekompatibilní dvojice kachlíků: ::$V$ = {(p, q) | spodní barva Tp se neshoduje s horní barvou Tq}, ::$H$ = {(p, q) | pravá barva Tp se neshoduje s levou barvou Tq}. Množina V obsahuje dvojice typů, jež nemohou být umístěny nad sebe, tedy vertikálně. Množina H obsahuje dvojice typů, jež nemohou být umístěny vedle sebe, tedy horizontálně. Podobné množiny si definujeme i pro barvy na okrajích, pro i = 1, . . . , s definujeme Ui, Bi, Li, Ri. ::$U_j$ = {k | horní barva Tk se shoduje s barvou horního okraje S v j-tém sloupci} ::$B_j$ = {k | spodní barva Tk se shoduje s barvou spodního okraje S v j-tém sloupci} ::$L_j$ = {k | levá barva Tk se shoduje s barvou levého okraje S na j-tém řádku} ::$R_j$ = {k | pravá barva Tk se shoduje s barvou pravého okraje S na j-tém řádku} Množina $Ui$ tedy obsahuje typy kachlíků, jež mohou být umístěny na políčko $S[1, i]$, množina $Bi$ obsahuje typy kachlíků, jež mohou být umístěny na políčko $S[s, i]$, množina $Li$ obsahuje typy kachlíků, jež mohou být umístěny na políčko $S[i, 1]$, a konečně $Ri$ obsahuje typy kachlíků, jež mohou být umístěny na políčko $S[i, s]$. Konstrukci formule $φ$ popíšeme po částech. Formule KNF je definovaná množinou svých klauzulí (jejich konjunkcí získáme danou formuli). Konjunkce několika KNF je KNF. 1. Pro $\{ i, j = 1, . . . , s \}$ definujeme: $C_{i, j} = (x_{i,j,1}\vee x_{i,j,2} \vee ... \vee x_{i,j,K} )$. Tyto klauzule v budoucí CNF vynucují, že na každém políčku je aspoň 1 typ kachlíku. 1. Pro $\{ i, j = 1, . . . , s \}$ definujeme: $\alpha_{i, j} = \wedge_{k = 1..K} \wedge_{l=(k+1)..K}(\neg x_{i,j,k} \vee \neg x_{i,j,l})$. Tyto klauzule vynucují, že každému políčku $S[i, j]$ je přiřazen nejvýš jeden typ kachlíku. 1. Pro $\{ i, j = 1, . . . , s \}$ definujeme: $\beta_{i, j} = C_{i, j} \wedge \alpha_{i,j}$. Formule $βi, j$ je tedy splněna, pokud políčku $S[i, j]$ přiřadíme právě jeden typ kachlíku. 1. Pro $\{ 1 ≤ i ≤ (s – 1) \}, \{ 1 ≤ j ≤ s \}$ definujeme: $\gamma_{i, j} = \wedge_{(p, q) \in V} (\neg x_{i, j,p} \vee \neg x_{(i + 1),j,q})$. Formule $\gamma_{i, j}$ je splněna, pokud nad sebou umístěným políčkům $S[i, j], S[(i + 1), j]$ nejsou přiřazeny nekompatibilní typy kachlíků. 1. Pro $\{ 1 ≤ i ≤ s \}, \{ 1 ≤ j ≤ (s – 1) \}$ definujeme: $\delta_{i, j} = \wedge_{(p, q) \in H} (\neg x_{i, j,p} \vee \neg x_{i,(j + 1),q})$. Formule $\delta_{i, j}$ je splněna, pokud vedle sebe umístěným políčkům $S[i, j], S[i, (j + 1)]$ nejsou přiřazeny nekompatibilní typy kachlíků. 1. Definujeme: $\epsilon_u = \wedge_{j=1..s} [ \vee_{k\in U_j} x_{1, j, k}]$. Formule je splněna, pokud je na každém políčku v prvním řádku kachlík s barvou shodnou s příslušným horním okrajem. 1. Definujeme: $\epsilon_b = \wedge_{j=1..s} [ \vee_{k\in B_j} x_{s, j, k}]$. Formule je splněna, pokud je na každém políčku v nejspodnějším řádku kachlík s barvou shodnou s příslušným spodním okrajem. 1. Definujeme: $\epsilon_l = \wedge_{i=1..s} [ \vee_{k\in L_i} x_{i, 1, k}]$. Formule je splněna, pokud je na každém políčku v nejlevějším sloupci kachlík s barvou shodnou s příslušným levým okrajem. 1. Definujeme: $\epsilon_r = \wedge_{i=1..s} [ \vee_{k\in R_i} x_{i, s, k}]$. Formule je splněna, pokud je na každém políčku v nejlevějším sloupci kachlík s barvou shodnou s příslušným levým okrajem. Formuli $φ$ dostaneme jako konjunkci všech formulí výše: ::$φ = [\wedge_{i = 1..s; j = 1..s} \beta_{i, j}] \wedge [\wedge_{i = 1..(s - 1); j = 1..s} (\gamma_{i, j} \wedge \delta_{j,i})] \wedge \epsilon_u \wedge \epsilon_b \wedge \epsilon_r \wedge \epsilon_l$. Z konstrukce okamžitě vyplývá, že $φ$ je formule v KNF a že velikost $φ$ je polynomiální v s a $|K|$, a v polynomiálním čase lze $φ$ i zkonstruovat. Zbývá ukázat, že pro výchozí instanci problému Kachlíkování existuje přípustné vykachlíčkování, právě když $φ$ je splnitelná formule. Ve skutečnosti ukážeme, že ze splňujícího ohodnocení formule $φ$ lze vyčíst přípustné vykachlíkování čtvercové sítě $S$ a naopak z přípustného vykachlíkování lze určit splňující ohodnocení formule $φ$. Předpokládejme nejprve, že existuje přípustné vykachlíčkování S kachlíky z $K$. Označme pomocí $S[i, j]$ index typu kachlíku, který je na i-tém řádku a j-tém sloupci. Definujme $xi, j, k = 1$ právě když je na políčku $S[i, j]$ umístňen kachlík $Tk$. Není těžké ověřit, že každá z podformulí $βi ,j, γi, j, δi, j, εu, εb, εl, εr$ je tímto ohodnocením splněna, a tedy že i celá formule $φ$ je splněna. Předpokládejme na druhou stranu, že existuje splňující ohodnocení formule $φ$ a pomocí $v[i, j, k]$ označme hodnotu přiřazenou proměnné $xi, j, k$ ve splňujícím ohodnocení. Díky tomu, že ohodnocení splňuje i formuli $βi,j$, existuje pro každé $\{ i, j = 1, . . . , s \}$ právě jedno $k ∈ \{1, . . . , |K|\}$, pro kterou je $v[i, j, k] = 1$. Na pozici $S[i, j]$ tedy dáme kachlík toho typu $Tk$, pro který je $v[i, j, k] = 1$. Lze snadno ověřit, že podmínky zakódované do formulí $γi, j, δi, j, εu, εb, εl, εr$ zaručují, že tímto způsobem obdržíme přípustné vykachlíkování $S$.