Alternirajući Turingov stroj

U računskoj teoriji složenosti, alternirajući Turingov stroj je nedeterministički Turingov stroj (ATS) sa pravilom prihvaćanja izračunavanja koje poopćava pravila korištena u definiciji klasa složenosti NP i co-NP. Koncept ATS su postavili Chandra i Stockmeyer 1976. (vidjeti reference).

Definicije

Neformalni opis

Definicija klase NP koristi "egzistencijalni način rada" izračunavanja: ako neki izbor vodi do prihvaćajućeg stanja, tada je cijelo izračunavanje prihvaćajuće. Definicija klase co-NP koristi "univerzalni način rada" izračunavanja: ako svi izbori vode do prihvaćajućeg stanja, tada je i cijelo izračunavanje prihvaćajuće. Alternirajući Turingov stroj (ili preciznije, definicija prihvaćanja takvog stroja) alternira između ovih načina rada.

Alternirajući Turingov stroj je nedeterministički Turingov stroj čija su stanja podijeljena u dva skupa: egzistencijalna stanja i univerzalna stanja. Egzistencijalno je stanje prihvatjlivo ako neki prijelaz vodi do prihvatljivog stanja, dok je univerzalno stanje prihvatljivo ako svaki prijelaz vodi do prihvatljivog stanja. (Stoga univerzalno stanje bez prijelaza bezuvjetno prihvaća, dok egzistencijalno stanje bez prijelaza bezuvjetno odbija). Stroj kao cjelina prihvaća ukoliko je početno stanje prihvaćajuće.

Formalna definicija

Formalno, (jednotračni) alternirajući Turingov stroj je uređena petorka $M=(Q,\Gamma ,\delta ,q_{0},g)$ pri čemu je

• $Q$ konačan skup stanja
• $\Gamma$ je konačna abeceda trake
• $\delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})$ funkcija prijelaza (ili tranzicijska funkcija) (L pomiče glavu u lijevo dok R pomiče glavu u desno)
• $q_{0}\in Q$ početno stanje
• $g:Q\rightarrow \{\wedge ,\vee ,prihvati,odbaci\}$ specificira tip svakog stanja

Ako je M u stanju $q\in Q$ sa $g(q)=prihvati$, za konfiguraciju kažemo da je prihvaćajuća (ili prihvatljiva), a ako je $g(q)=odbaci$, za konfiguraciju kažemo da je odbacujuća. Za konfiguraciju sa $g(q)=\wedge$ kažemo da je prihvaćajuća ako su sve konfiguracije dohvatljive u jednom koraku prihvaćajuće, odnosno odbacujuća ako je neka konfiguracija dohvatljiva u jednom koraku odbacujuća. Za konfiguraciju sa $g(q)=\vee$ se kaže da je prihvaćajuća ako postoji neka konfiguracija dohvatljiva u jednom koraku koja je prihvaćajuća i odbacujuća kada su sve konfiguracije dohvatljive u jednom koraku odbacujuće (ovo je tip svih stanja u NTS). Za M se kaže da prihvaća ulazni niz w ako je početna konfiguracija od M (stanje od M je $q_{0}$, glava je na krajnjem lijevom kraju trake, i sadržaj trake jest ulazni niz w) prihvaćajuća, odnosno odbija ako je početna konfiguracija odbacujuća.

Stroj sa k alternacija

Alternirajući Turingov stroj sa k alternacija je alternirajući Turingov stroj koji skače iz egzistencijalnog u univerzalno stanje, i obrnuto, no ne više od k-1 puta. (To je u biti alternirajući Turingov stroj čija su stanja podijeljena u k skupova. Stanja u parno pobrojanim skupovima su univerzalna, dok su stanja u neparno pobrojanim skupovima egzistencijalna (može i obrnuto). Stroj nema prijelaza između stanja u skupu i i stanja u skupu j < i.)

Na primjer, razmatranjem problema minimizacije kruga - za dani krug A koji računa bulovsku funkciju f i broj n, odredi postoji li krug sa najviše n vrata koji računa istu funkciju f. Alternirajući Turingov stroj sa jednom alternacijom, počinjući u egzistencijalnom stanju, može riješiti problem u polinomnom vremenu (pogađanjem kruga B sa najviše n stanja, i tada skačući u univerzalno stanje, pogađajući ulaz, i provjeravajući da izlaz od B za taj ulaz odgovara izlazu od A na tom ulazu).

Alternirajući Turingov stroj sa k alternacija, koji započinje rad u egzistencijalnom (respektivno, univerzalnom) stanju, može odlučiti sve probleme u klasi složenosti $\Sigma _{k}{\rm {P}}$ (respektivno, $\Pi _{k}{\rm {P}}$) u polinomnom vremenu. Pogledati članak o polinomnoj hijerarhiji.

Ograničenja na resurse

Prilikom odlučivanja je li konfiguracija ATS prihvaćajuća ili odbacujuća koristeći gornju definiciju, nije nužno provjeriti sve konfiguracije dohvatljive iz trenutne konfiguracije. Posebice, egzistencijalne se konfiguracije mogu označiti kao prihvaćajuće ukoliko je prihvaćajuća bilo koja sljedbenička konfiguracija, dok se univerzalne konfiguracije mogu označiti kao odbacujuće ukoliko je odbacujuća bilo koja sljedbenička konfiguracija.

ATS odlučuje formalni jezik u vremenu $t(n)$ ako, za bilo koji ulaz duljine $n$, ispitivanje konfiguracija u najviše $t(n)$ koraka je dovoljno za označavanje početne konfiguracije prihvaćajućom ili odbacujućom. ATS odlučuje jezik u prostoru $s(n)$ ako je dovoljno ispitivanje konfiguracija koje ne modificraju sadržaj trake izvan opsega ćelije na poziciji $s(n)$ u lijevo.

Za jezik kojeg neki ATS odlučuje u vremenu $c\cdot t(n)$ za neku konstantu $c>0$ se kaže da je u klasi ${\rm {ATIME}}(t(n))$, a za jezik odlučiv u prostoru $c\cdot s(n)$ se kaže da je u klasi ${\rm {ASPACE}}(s(n))$.

Primjer

Možda najjednostavniji primjer za rješavanje alternirajućim strojevima jest problem kvantificiranih bulovskih formula, koji predstavlja poopćenje problema ispunjivosti bulovskih formula, u kojem svaka varijabla može biti vezana egzistencijalnim ili univerzalnim kvantifikatorom. Alternirajući stroj grana egzistencijalno kako bi isprobavao sve moguće vrijednosti egzistencijalno kvantificiranih varijabli, i univerzalno kako bi isprobavao sve moguće vrijednosti univerzalno kvantificiranih varijabli, s lijeve na desnu stranu u redoslijedu vezanja. Nakon odlučivanja o vrijednosti za sve kvantificirane varijable, stroj prihvaća ili odbija ovisno o tome daje li evaluacija bulovske formule logičku istinu ili laž. Stoga u egzistencijalno kvantificiranim varijablama stroj prihvaća ukoliko varijabla može biti supstituirana vrijednošću koja uzrokuje ispunjenje ostatka problema, dok u univerzalno kvantificiranim varijablama stroj prihvaća ukoliko bilo koja vrijednost može biti supstituirana pri čemu je ostatak problema ispunjiv.

Takav stroj odlučuje kvantificirane bulovske formule u vremenu $n^{2}$ i prostoru $n$.

Problem bulovske ispunjivosti se može promatrati kao poseban slučaj u kojem su sve varijable egzistencijalno kvantificirane, dozvoljavajući uobičajeni nedeterminizam, koji koristi samo egzistencijalna grananja, da bi se učinkovito riješio.

Klase složenosti i usporedba sa determinističkim Turingovim strojevima

Sljedeće je klase složenosti korisno definirati za ATS:

• ${\rm {AP}}=\bigcup _{k>0}{\rm {ATIME}}(n^{k})$ su jezici odlučivi u polinomnom vremenu
• ${\rm {APSPACE}}=\bigcup _{k>0}{\rm {ASPACE}}(n^{k})$ su jezici odlučivi u polinomnom prostoru
• ${\rm {AEXPTIME}}=\bigcup _{k>0}{\rm {ATIME}}(k^{n})$ su jezici odlučivi u eksponencijalnom vremenu

Ove su klase slične definicijama klasa P, PSPACE i EXPTIME, uzimajući u obzir resurse koje troši ATS za razliku od determinističkog Turingovog stroja. Chandra, Kozen, i Stockmeyer su dokazali sljedeće važne teoreme:

• AP = PSPACE
• APSPACE = EXPTIME
• AEXPTIME = EXPSPACE

Ovo je izraženo u tezi o paralelnom računanju.

Izvori

• Chandra, A.K. and Kozen, D.C. and Stockmeyer, L.J., 'Alternation', Journal of the ACM, Volume 28, Issue 1, pp. 114–133, 1981.
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X  Section 10.3: Alternation, pp. 348–354.
• Michael Sipser (2006). Introduction to the Theory of Computation, 2nd ed.. PWS Publishing. ISBN 0-534-95097-3  Section 10.3: Alternation, pp. 380–386.
• Christos Papadimitriou (1993). Computational Complexity (1st edition ed.). Addison Wesley. ISBN 0-201-53082-1  Section 16.2: Alternation, pp. 399–401.