EXPSPACE

În teoria complexității , EXPSPACE este ansamblul tuturor problemelor de decizie care pot fi rezolvate de o mașină Turing deterministă în spațiul O (2 ^{p ( n )} ), unde p ( n ) este o funcție polinomială a lui n . (Unii autori limitează p ( n ) la a fi o funcție liniară , dar în schimb majoritatea autorilor numesc clasa rezultată ESPACE .) Dacă folosim în schimb o mașină nedeterministă , obținem clasa NEXPSPACE , care este egală cu EXPSPACE prin teorema lui Savitch .

În ceea ce privește DSpace și N-Space ,

{\mbox{EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}(2^{n^{k}})=\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(2^{n^{k}})

{\ displaystyle {\ mbox {EXPSPACE}} = \ bigcup _ {k \ in \ mathbb {N}} {\ mbox {DSPACE}} (2 ^ {n ^ {k}}) = \ bigcup _ {k \ in \ mathbb {N}} {\ mbox {NSPACE}} (2 ^ {n ^ {k}})}

{\ displaystyle {\ mbox {EXPSPACE}} = \ bigcup _ {k \ in \ mathbb {N}} {\ mbox {DSPACE}} (2 ^ {n ^ {k}}) = \ bigcup _ {k \ in \ mathbb {N}} {\ mbox {NSPACE}} (2 ^ {n ^ {k}})}

O problemă de decizie este EXPSPACE-completă dacă este în EXPSPACE și fiecare problemă din EXPSPACE are o reducere de timp polinomială . Cu alte cuvinte, există un algoritm de timp polinomial care transformă cererile uneia dintre celelalte cereri cu același răspuns. Problemele complete ale EXPSPACE ar putea fi considerate cele mai dificile probleme din EXPSPACE .

EXPSPACE este un superset strâns de PSPACE , NP și P și se crede că este un superset strâns de EXPTIME .

Un exemplu de problemă completă EXPSPACE este să recunoaștem dacă două expresii regulate reprezintă limbi diferite, unde expresiile sunt limitate la patru operatori: unire, concatenare , steaua lui Kleene (zero sau mai multe copii ale unei expresii) și cvadratură (două copii ale unei expresii ). ^[1]

Dacă lăsați steaua Kleene, atunci această problemă devine NEXPTIME -completă , care este ca EXPTIME-completă , cu excepția faptului că este definită în termeni de mașini de Turing nedeterministe, mai degrabă decât deterministe.

De asemenea, L. Berman a arătat în 1980 că problema verificării / falsificării oricărei afirmații de prim ordin despre numere reale care implică doar adunare și comparație (dar nu multiplicare ) se află în EXPSPACE .

Notă

^ Meyer, AR și L. Stockmeyer . Problema echivalenței pentru expresiile regulate cu pătrat necesită spațiu exponențial . Al 13-lea Simpozion IEEE privind comutarea și teoria automatelor , octombrie 1972, pp. 125-129.

Bibliografie

L. Berman Complexitatea teoriilor logice , Theoretical Computer Science 11: 71-78, 1980.
Michael Sipser , Introducere în teoria calculelor , PWS Publishing, 1997, ISBN 0-534-94728-X . Secțiunea 9.1.1: „Completitatea spațiului exponențial”, pp. 313-317. Dovediți că determinarea echivalenței expresiei regulate cu exponențierea este EXPSPACE-complet.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] Meyer, AR și L. Stockmeyer . Problema echivalenței pentru expresiile regulate cu pătrat necesită spațiu exponențial . Al 13-lea Simpozion IEEE privind comutarea și teoria automatelor , octombrie 1972, pp. 125-129.

[1]