Nedeterministický Turingův stroj → SAT

Dle Cookovy věty lze převést v polynomiálním čase libovolný nedeterministický Turingův stroj na problém splnitelnosti booleovských formulí v konjunktivním normálním tvaru (CNF SAT).

Důsledkem této věty je vymezení skupiny úloh, které jsou nejtěžší v rámci všech problémů třídy NP. O těchto úlohách, na které lze převést v polynomiálním čase libovolnou jinou úlohu z NP, říkáme, že jsou NP-úplné (NP-complete).

Idea důkazu

Nejprve je zapotřebí ukázat, že je $SAT \\in NP$ , což je ale zřejmé, protože lze vyhodnotit ANO-instanci v polynomiálním čase (přiřazením jednotlivých hodnot a vyhodnocením formulí).

Mějme Turingův stroj , který je dán z množinou stavů , vstupní abecedou $\\Sigma$ , páskovou abecedou $\\Gamma$ , přechodovou funkcí $\\delta$ , počátečním stavem $q_{0}$ a koncovým stavem $q_{f}$ . Zároveň předpokládejme, že přijímá slovo v p(n) krocích ( je polynom).

Pomocné logické proměnné

Zaveďme nové logické proměnné:

$h_{i,\\; j}$ , kde i a j nabývají hodnot $\\{0, \\cdots,\\; p_{n}\\}$ . Pokud je hodnota proměnné $h_{i,j}$ PRAVDA, pak to znamená, že hlava stroje M čte v čase i j-té pole pásky.
$s_{i}^{q}$ , kde i nabývá hodnot $\\{0, \\cdots,\\; p_{n}\\}$ a $q \\in Q$ . Pokud je hodnota proměnné $s_{i}^{q}$ PRAVDA, pak to znamená, že je M v čase i ve stavu q.
$t_{i,\\; j}^{A}$ , i a j nabývají hodnot $\\{0, \\cdots,\\; p_{n}\\}$ , $A \\in \\Gamma$ . Pokud je hodnota proměnné $t_{i,\\; j}^{A}$ PRAVDA, pak to znamená, že v j-tém poli je v čase i páskový symbol A.

Formulace

Nyní formulujme práci Turingova stroje jako úlohu SAT.

První podmínkou je, že je stroj M vždy alespoň v jednom stavu.

$\\bigvee_{q \\in Q} s_{i}^{q}$

Turingův stroj nesmí být ve více různých stavech zároveň.

$\\bigwedge_{q \\neq q'} \\lnot s_{i}^{q} \\vee \\lnot s_{i}^{q'}$

V počátečním stavu je Turingův stroj v ve stavu $q_{0}$ , hlava čte první pole pásky a v prvních n polích je vstupní slovo w.

$s_{0}^{q_{0}} \\wedge h_{0,\\; 1} \\wedge t_{0,1}^{a_{1}} \\wedge \\cdots \\wedge t_{0,\\; n}^{a_{n}} \\wedge t_{0,\\; n+1}^{B} \\wedge \\cdots \\wedge t_{0,\\; p(n)}^{B}$

Pokud je M v čase i ve stavu q a čte na j-tém poli symbol A a $\\delta(q,\\; A)$ obsahuje přechody $(p,\\; C,\\; D)$ , kde D = 1 znamená posun doprava a D = -1 posun doleva, pak lze tuto formuli zapsat jako:

$\\bigwedge_{j} \\bigwedge_{A \\in \\Gamma} ((s_{i}^{q} \\wedge h_{i, j} \\wedge t_{i,\\; j}^{A}) \\Rightarrow \\bigvee (s_{i+1}^{p} \\wedge t_{i+1,\\; j}^{C} \\wedge h_{i+1,\\; j+D}))$

Obsah všech polí kromě j-tého (aktuálně zpracovávaného) se v čase i+1 nemění.

$\\bigwedge_{j} \\bigwedge_{A \\in \\Gamma} ((\\lnot h_{i,\\; j} \\wedge t_{i,\\; j}^{A}) \\Rightarrow t_{i+1,\\; j}^{A})$

Turingův stroj skončí po vykonání programu ve stavu $q_{f}$ .

$s_{p(n)}^{q_{f}}$

Formule odpovídající Turingovu stroji vznikne jako konjunkce všech zde zmíněných formulí (v CNF) pro jednotlivé časové okamžiky ${0,\\; 1,\\; 2, \\cdots,\\; p(n)}$ .

Literatura

DEMLOVÁ, Marie. Teorie algoritmů : Text k přednášce.

Idea důkazu

Pomocné logické proměnné

Formulace

Literatura

Doporučujeme