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.

{ zpětná vazba }

Tweet		Delicious
Sdílet

Hodnocení (0): 0

Přečtěte si také

Diskuse

Článek zatím nemá žádné komentáře.