Image:Npc.jpg

:: 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

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲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

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲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

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: 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

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲1, i]

, množina $Bi$

obsahuje typy kachlíků, jež mohou být umístěny na políčko

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲s, i]

, množina $Li$ obsahuje typy kachlíků, jež mohou být umístěny na políčko

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲i, 1]

, a konečně $Ri$ obsahuje typy kachlíků, jež

mohou být umístěny na políčko

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: 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.

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

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲i, j]

   je přiřazen nejvýš jeden typ kachlíku.

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

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲i, j]

   přiřadíme právě jeden typ kachlíku.

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

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲i, j], S\[(i + …

   nejsou přiřazeny nekompatibilní typy kachlíků.

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

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲i, j], S\[i, (j…

   nejsou přiřazeny nekompatibilní typy kachlíků.

6. Definujeme:

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 30: …wedge_{j=1..s} \̲[̲ \vee_{k\in U_j…

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

7. Definujeme:

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 30: …wedge_{j=1..s} \̲[̲ \vee_{k\in B_j…

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

8. Definujeme:

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 30: …wedge_{i=1..s} \̲[̲ \vee_{k\in L_i…

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

9. Definujeme:

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 30: …wedge_{i=1..s} \̲[̲ \vee_{k\in R_i…

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

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: 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

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: 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í

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: 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

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: v\̲[̲i, j, k] = 1

. Na pozici

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲i, j]

tedy dáme kachlík toho typu $Tk$, pro který je

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: 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$.