KACHL

Zadání: Je zadaná množina barev B, čtvercová síť S (po obvodu obarvená barvami z B) a množina typů kachlíků K (každý typ je definován svojí horní, dolní, pravou a levou barvou).

Problém: Lze síť S vyplnit celou kachlíky z K (každý typ lze použít libovolně krát, nelze "otáčet") tak, aby A) barvy kachlíků přilehlé k obvodu sítě odpovídaly zadaným barvám na obvodu a B) aby každé dva sousední kachlíky měly v místě dotyku stejnou barvu?

Z definice NP víme, že problém R je v NP, když existuje polynomiální NTS $ M = (Q, Σ, δ, q_0, F ) $, který řeší R ( L(M)=L(R)_Y ). Abychom dokázali, že KACHL je NP-těžký, musíme umět jakýkoliv problém R převést na odpovídající zadání KACHL (= množina barev B + rozměry a obvod sítě S + použitelné typy kachlíků K) takové, které bude řešitelné, právě když se M nad daným vstupem zastaví.

Barvy

Množinu možných barev položme $ B = Σ ∪ (Q × Σ) ∪ (Q × \{\leftarrow,\rightarrow\}) $. Předpokládáme, že abeceda obsahuje prázdný symbol $ \lambda $.

Síť a barvy po obvodu

Stěna, kterou budeme kachličkovat bude dostatečně dlouhá i vysoká (max. počet kroků algoritmu). Na jejím horním okraji bude zleva napsáno slovo x (pro každou hlavičku sloupce kachlíků jeden symbol x_i ∈ x) a zbytek doplníme prázdnými znaky pásky (λ). Přesněji: hlavička prvního sloupce nebude x₁, ale dvojice (q₀, x₁). Takže, na horním okraji stěny je zakódováno vstupní slovo x, které je zapsáno na pásce, a hlava NTS stojí na nejlevějším konci pásky, na symbolu x₁ a je v počátečním stavu q₀.

Typy kachlíků

Nyní budeme dlaždičkovat koupelnu shora dolů, řádek po řádku. Každý řádek bude odpovídat jedné konfiguraci turingova stroje. V každém řádku tedy uvidíme aktuální vzhled pásky, dále uvidíme, nad kterým symbolem na pásce je hlava TS a v jakém stavu se nachází. Budeme tedy potřebovat několik druhů kachlíků. Jedna skupina kachlíků bude reprezentovat pozici na pásce, na které je aktuálně hlava ve stavu q, druhá skupina kachlíků bude reprezentovat pozice pásky, nad kterými hlava není. Je jasné, že když nad danou pozicí pásky není hlava, páska se v tom místě nemění a dvě po sobě jdoucí konfigurace stroje budou tedy mít v tomto místě pásky stejný symbol. Druhá skupina kachlíků tedy bude "kopírovací" - bude kopírovat symbol z předchozí konfigurace (z řádku nad ní) a nebude nic měnit:

pro všechna s ∈ Σ (abeceda pásky)

První skupina kachlíků tedy bude reprezentovat pozici pásky se symbolem s, nad kterou je hlava ve stavu q a která přechází přechodovou funkcí δ do stavu q', zapíše na pozici symbol s' a posune se doprava, doleva, nebo zůstane. Vzhledem k tomu, že se jedná o NTS program, není přechodová funkce funkcí, ale zobrazením, kde $ \delta(q,s) \subset \left \{ Q \times \Sigma \times \left \{ \leftarrow,\rightarrow,\circ \right \} \right \} $. Takže pro dvojici (q,s) může existovat několik dlaždiček:

pro všechna q,s,q',s' taková, že $ (q',s',\circ) \in \delta (q,s) $

pro všechna q,s,q',s' taková, že $ (q',s',\rightarrow) \in \delta (q,s) $

pro všechna q,s,q',s' taková, že $ (q',s',\leftarrow) \in \delta (q,s) $

Kromě toho budeme potřebovat ještě další dva "kopírovací" kachlíky, které budou kompatibilní s dvěma předchozími a budou kopírovat symbol s shora a stav q zleva nebo zprava:

pro všechna q a všechna s

pro všechna q a všechna s

Vše máme připraveno, můžeme kachličkovat. Čistě hypoteticky, pokud by problém zněl "Lze nahradit vstupní slovo x ∈ {0,1}* na pásce stejně dlouhou posloupností jedniček?", vystačili bychom si s jednoduchoučkým DETERMINISTICKÝM programem (zatím neřešíme úklid a koncový stav):

Vzhledem k tomu, že program je deterministický, má pro stejný vstup jen jeden přímočarý výpočet a proto bude i vykachličkování přímočaré, protože se nebudeme muset nikde rozhodovat, kterou z možných cest jít. Na následujícím obrázku vidíme konfiguraci stroje po prvním kroku (spodní okraj prvního řádku kachliček):

Dále budeme pokračovat stejným způsobem:

Tím jsme původní slovo 00010 nahradili slovem 11111. Stroj by po sobě měl uklidit, a skončit v konfiguraci (q_Y,λ),λ,λ,... To ovšem vyžaduje doplnění uvedeného programu o uklízecí část a nový koncový stav q_Y (samozřejmě v návaznosti na změnu δ i nové kachličky). Máme-li koupelnu příliš vysokou, budeme potřebovat ještě poslední druh kachlíků:

Kdybychom měli nedeterministický program, bude i vykachličkování nedeterministické a museli bychom správné vykachličkování nějakým způsobem uhodnout, nebo pomocí "brutal force" zkusit všechny možné kombinace a u každé testovat, zda jsou podmínky barevnosti sousedních stran splněné ( O(k²ⁿn²) ). Tím jsme ukázali, že pomocí vykachličkování umíme najít přijímací výpočet libovolného NTS programu, a tudíž vyřešit libovolný NP problém, a tudíž

$ \forall P \in NP: L(P)_Y < L(KACHL)_Y $