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 M, který je dán z množinou stavů Q, 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 M přijímá slovo w v p(n) krocích (p 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.







Doporučujeme

Internet pro vaši firmu na míru