Střídavý Turingův stroj - Alternating Turing machine

v teorie výpočetní složitosti, an střídavý Turingův stroj (bankomat) je nedeterministický Turingův stroj (NTM) s pravidlem pro přijímání výpočtů, které zobecňuje pravidla použitá při definici třídy složitosti NP a co-NP. Koncept bankomatu byl stanoven Chandra a Stockmeyer^[1] a nezávisle na Kozen^[2] v roce 1976, se společnou publikací časopisu v roce 1981.^[3]

Definice

Neformální popis

Definice NP používá existenční režim výpočtu: pokud žádný volba vede k přijímajícímu stavu, poté přijímá celý výpočet. Definice co-NP používá univerzální režim výpočtu: pouze pokud Všechno volby vedou k přijímajícímu stavu, akceptuje celý výpočet. Mezi těmito režimy se střídá Turingův stroj (nebo přesněji definice přijetí takového stroje).

An střídavý Turingův stroj je nedeterministický Turingův stroj jejichž stavy jsou rozděleny do dvou sad: existenční stavy a univerzální státy. Existenciální stav přijímá, pokud nějaký přechod vede k přijímajícímu stavu; univerzální stát přijímá, pokud každý přechod vede k přijímajícímu stavu. (Univerzální stát bez přechodů tedy bezpodmínečně přijímá; existenční stav bez přechodů bezpodmínečně odmítá). Stroj jako celek přijímá, pokud přijímá počáteční stav.

Formální definice

Formálně a (one-tape) střídavý Turingův stroj je 5-n-tice ${ displaystyle M = (Q, Gamma, delta, q_ {0}, g)}$ kde

${ displaystyle Q}$ je konečná množina stavů
${ displaystyle Gamma}$ je konečná páska abeceda
${ displaystyle delta: Q times Gamma rightarrow { mathcal {P}} (Q times Gamma times {L, R })}$ se nazývá přechodová funkce (L posune hlavu doleva a R posune hlavu doprava)
${ displaystyle q_ {0} v Q}$ je počáteční stav
${ displaystyle g: Q rightarrow { klín, vee, přijmout, odmítnout }}$ určuje typ každého státu

Li M je ve stavu ${ displaystyle q v Q}$ s ${ displaystyle g (q) = přijmout}$ pak se říká, že tato konfigurace je přijímání, a pokud ${ displaystyle g (q) = odmítnout}$ konfigurace se říká, že je odmítnutí. Konfigurace s ${ displaystyle g (q) = klín}$ se říká, že přijímá, pokud všechny konfigurace dosažitelné v jednom kroku přijímají, a odmítá, pokud některá konfigurace dosažitelná v jednom kroku odmítá. Konfigurace s ${ displaystyle g (q) = vee}$ se říká, že přijímá, když existuje nějaká konfigurace dosažitelná v jednom kroku, která přijímá a odmítá, když všechny konfigurace dosažitelné v jednom kroku odmítají (to je typ všech stavů v NTM). M říká se, že přijímá vstupní řetězec w pokud je počáteční konfigurace M (stát M je ${ displaystyle q_ {0}}$ , hlava je na levém konci pásky a páska obsahuje w) přijímá a odmítá, pokud odmítá původní konfiguraci.

Omezení zdrojů

Při rozhodování, zda konfigurace bankomatu přijímá nebo odmítá pomocí výše uvedené definice, není nutné zkoumat všechny konfigurace dosažitelné z aktuální konfigurace. Zejména lze existenciální konfiguraci označit jako přijímající, pokud se zjistí, že přijímá jakoukoli následnou konfiguraci, a univerzální konfiguraci lze označit jako odmítnout, pokud se zjistí, že některá následná konfigurace odmítá.

Bankomat rozhodne a formální jazyk včas ${ displaystyle t (n)}$ pokud na jakémkoli zadání délky $n$ , zkoumání konfigurací pouze do ${ displaystyle t (n)}$ kroky je dostatečné k označení počáteční konfigurace jako přijetí nebo odmítnutí. Bankomat rozhoduje o jazyce ve vesmíru ${ displaystyle s (n)}$ při zkoumání konfigurací, které nemění buňky pásky za ${ displaystyle s (n)}$ buňka zleva je dostačující.

Jazyk, o kterém rozhoduje nějaký bankomat včas ${ displaystyle c cdot t (n)}$ pro nějakou konstantu ${ displaystyle c> 0}$ je prý ve třídě ${ displaystyle { mathsf {ATIME}} (t (n))}$ a jazyk rozhodnutý ve vesmíru ${ displaystyle c cdot s (n)}$ je prý ve třídě ${ displaystyle { mathsf {ASPACE}} (s (n))}$ .

Příklad

Snad nejjednodušší problém, který mají alternující stroje vyřešit, je kvantifikovaný problém s booleovským vzorcem, což je zobecnění Booleovský problém uspokojivosti ve kterém může být každá proměnná vázána existenčním nebo univerzálním kvantifikátorem. Střídavý stroj se větví existenciálně, aby vyzkoušel všechny možné hodnoty existenciálně kvantifikované proměnné a univerzálně vyzkoušel všechny možné hodnoty univerzálně kvantifikované proměnné, v pořadí zleva doprava, ve kterém jsou vázány. Po rozhodnutí o hodnotě pro všechny kvantifikované proměnné stroj přijme, pokud se výsledný booleovský vzorec vyhodnotí jako true, a odmítne, pokud se vyhodnotí jako false. U existenciálně kvantifikované proměnné tedy stroj přijímá, pokud lze za proměnnou nahradit hodnotu, která činí zbývající problém uspokojivým, a u univerzálně kvantifikované proměnné stroj přijímá, pokud lze nahradit jakoukoli hodnotu a zbývající problém je uspokojivý.

Takový stroj rozhoduje kvantifikované booleovské vzorce v čase ${ displaystyle n ^ {2}}$ a vesmír ${ displaystyle n}$ .

Na problém Booleovské uspokojivosti lze pohlížet jako na speciální případ, kdy jsou všechny proměnné existenciálně kvantifikovány, což umožňuje efektivní nedeterminismus, který využívá pouze existenční větvení, k efektivnímu řešení.

Třídy složitosti a srovnání s deterministickými Turingovými stroji

Následující třídy složitosti je užitečné definovat pro bankomaty:

${ displaystyle { mathsf {AP}} = bigcup _ {k> 0} { mathsf {ATIME}} (n ^ {k})}$ jsou jazyky, o kterých lze rozhodnout v polynomiálním čase
${ displaystyle { mathsf {APSPACE}} = bigcup _ {k> 0} { mathsf {ASPACE}} (n ^ {k})}$ jsou jazyky, o kterých lze rozhodnout v polynomiálním prostoru
${ displaystyle { mathsf {AEXPTIME}} = bigcup _ {k> 0} { mathsf {ATIME}} (2 ^ {n ^ {k}})}$ jsou jazyky, o nichž lze rozhodnout v exponenciálním čase

Jsou podobné definicím P, PSPACE, a EXPTIME, vzhledem k prostředkům používaným bankomatem spíše než k deterministickému Turingovu stroji. Chandra, Kozen a Stockmeyer^[3] prokázané věty

ALOGSPACE = P
AP = PSPACE
APSPACE = EXPTIME
AEXPTIME = EXPSPACE
${ displaystyle { mathsf {ASPACE}} (f (n)) = bigcup _ {c> 0} { mathsf {DTIME}} (2 ^ {cf (n)}) = { mathsf {DTIME}} (2 ^ {O (f (n))})}$
${ displaystyle { mathsf {ATIME}} (g (n)) subseteq { mathsf {DSPACE}} (g (n))}$
${ displaystyle { mathsf {NSPACE}} (g (n)) subseteq bigcup _ {c> 0} { mathsf {ATIME}} (c krát g (n) ^ {2}),}$

když ${ displaystyle f (n) geq log (n)}$ a ${ Displaystyle g (n) geq log (n)}$ .

Obecnější formu těchto vztahů vyjadřuje paralelní výpočetní práce.

Ohraničené střídání

Definice

An střídavý Turingův stroj s k střídání je střídavý Turingův stroj, který nepřepíná z existenčního do univerzálního stavu nebo naopak o více než k-1krát. (Jedná se o střídavý Turingův stroj, jehož stavy jsou rozděleny na k sady. Stavy v sadách se sudými čísly jsou univerzální a stavy v sadách s lichými čísly jsou existenční (nebo naopak). Stroj nemá žádné přechody mezi stavem v sadě i a stav v sadě j < i.)

${ displaystyle { mathsf {ATIME}} (C, j) = Sigma _ {j} { mathsf {TIME}} (C)}$ je třída funkce v čase ${ displaystyle f v C}$ počínaje existenčním stavem a střídáním nanejvýš ${ displaystyle j-1}$ krát. Říká se tomu $j$ Třetí úroveň ${ displaystyle { mathsf {TIME}} (C)}$ hierarchie.

${ displaystyle { mathsf {coATIME}} (C, j) = Pi _ {j} { mathsf {TIME}} (C)}$ je stejná třída, ale počínaje univerzálním stavem je doplňkem jazyka ${ displaystyle { mathsf {ATIME}} (f, j)}$ .

${ displaystyle { mathsf {ASPACE}} (C, j) = Sigma _ {j} { mathsf {SPACE}} (C)}$ je definován podobně pro výpočet ohraničený prostorem.

Příklad

Zvažte problém s minimalizací obvodu: daný obvod A výpočetní technika a Booleovská funkce F a číslo n, určete, zda existuje obvod s maximálně n brány, které počítají stejnou funkci F. Střídavý Turingův stroj s jednou alternácí, začínající v existenciálním stavu, může tento problém vyřešit v polynomiálním čase (hádáním obvodu B maximálně n brány, poté přepnutí do univerzálního stavu, hádání vstupu a kontrola, zda je výstup z B na tomto vstupu odpovídá výstupu A na tomto vstupu).

Spadající třídy

Říká se, že hierarchie zhroutí se na úroveň $j$ pokud je každý jazyk na úrovni ${ displaystyle k geq j}$ hierarchie je na její úrovni $j$ .

Jako důsledek Immerman – Szelepcsényiho věta, hierarchie logaritmického prostoru se zhroutí na svou první úroveň.^[4] Jako důsledek ${ displaystyle { mathsf {SPACE}} (f)}$ hierarchie se zhroutí na svou první úroveň, když ${ displaystyle f = Omega ( log)}$ je prostor konstruovatelný^{[Citace je zapotřebí ]}.

Speciální případy

Střídavý Turingův stroj v polynomiálním čase s k alternace, začínající v existenciálním (respektive univerzálním) stavu, mohou rozhodnout o všech problémech ve třídě ${ displaystyle Sigma _ {k} ^ {p}}$ (respektive ${ displaystyle Pi _ {k} ^ {p}}$ ).^[5]Tyto třídy jsou někdy označovány ${ displaystyle Sigma _ {k} { rm {P}}}$ a ${ displaystyle Pi _ {k} { rm {P}}}$ Viz polynomiální hierarchie článek pro podrobnosti.

Dalším zvláštním případem časových hierarchií je logaritmická hierarchie.

Reference

^ Chandra, Ashok K .; Stockmeyer, Larry J. (1976). "Střídání". Proc. 17. IEEE Symp. o základech informatiky. Houston, Texas. 98–108. doi:10.1109 / SFCS.1976.4.
^ Kozen, D. (1976). "O paralelismu u Turingových strojů". Proc. 17. IEEE Symp. o základech informatiky. Houston, Texas. str. 89–97. doi:10.1109 / SFCS.1976.20. hdl:1813/7056.
^ ^A ^b Chandra, Ashok K .; Kozen, Dexter C .; Stockmeyer, Larry J. (1981). "Střídání" (PDF). Deník ACM. 28 (1): 114–133. doi:10.1145/322234.322243. Archivovány od originál (PDF) 12. dubna 2016.
^ Immerman, Neil (1988). „Nedeterministický prostor je uzavřen doplňováním“ (PDF). SIAM Journal on Computing. 17 (5): 935–938. CiteSeerX 10.1.1.54.5941. doi:10.1137/0217058.
^ Kozen, Dexter (2006). Teorie výpočtu. Springer-Verlag. str.58. ISBN 9781846282973.

Další čtení

Michael Sipser (2006). Úvod do teorie výpočtu, 2. vyd. PWS Publishing. ISBN 978-0-534-95097-2. Oddíl 10.3: Střídání, s. 380–386.
Christos Papadimitriou (1993). Výpočetní složitost (1. vyd.). Addison Wesley. ISBN 978-0-201-53082-7. Část 16.2: Střídání, s. 399–401.
Bakhadyr Khoussainov; Anil Nerode (2012). Teorie automatů a její aplikace. Springer Science & Business Media. ISBN 978-1-4612-0171-7.

[chasto-1] Chandra, Ashok K .; Stockmeyer, Larry J. (1976). "Střídání". Proc. 17. IEEE Symp. o základech informatiky. Houston, Texas. 98–108. doi:10.1109 / SFCS.1976.4.

[kozen-2] Kozen, D. (1976). "O paralelismu u Turingových strojů". Proc. 17. IEEE Symp. o základech informatiky. Houston, Texas. str. 89–97. doi:10.1109 / SFCS.1976.20. hdl:1813/7056.

[alternation-3] A ^b Chandra, Ashok K .; Kozen, Dexter C .; Stockmeyer, Larry J. (1981). "Střídání" (PDF). Deník ACM. 28 (1): 114–133. doi:10.1145/322234.322243. Archivovány od originál (PDF) 12. dubna 2016.

[4] Immerman, Neil (1988). „Nedeterministický prostor je uzavřen doplňováním“ (PDF). SIAM Journal on Computing. 17 (5): 935–938. CiteSeerX 10.1.1.54.5941. doi:10.1137/0217058.

[5] Kozen, Dexter (2006). Teorie výpočtu. Springer-Verlag. str.58. ISBN 9781846282973.

[1]

[2]

[3]

[4]

[5]