NSPACE

În teoria complexității , NSPACE desemnează o familie de clase de complexitate caracterizate prin complexitatea lor spațială pe o mașină de Turing nedeterministă .

Mai precis, este clasa problemelor de decizie care, pentru o intrare de dimensiune , pot fi decise de o mașină Turing nedeterministă care funcționează în spațiu . NUSPLAVSE(f(nu)){\ displaystyle {\ mathsf {NSPACE}} (f (n))}nu{\ displaystyle n}O(f(nu)){\ displaystyle {\ mathcal {O}} (f (n))}

Definiții

Clasele de complexitate NL , NPSPACE și NEXPSPACE sunt definite din familia NSPACE:

NUL=NUSPLAVSE(O(Buturuga⁡nu)){\ displaystyle {\ mathsf {NL}} = {\ mathsf {NSPACE}} ({\ mathcal {O}} (\ log n))}NUPSPLAVSE=⋃k∈NUNUSPLAVSE(nuk)=PSPLAVSE{\ displaystyle {\ mathsf {NPSPACE}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {NSPACE}} (n ^ {k}) = {\ mathsf {PSPACE}}}NUEXPSPLAVSE=⋃k∈NUNUSPLAVSE(2nuk)=EXPSPLAVSE{\ displaystyle {\ mathsf {NEXPSPACE}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {NSPACE}} \ left (2 ^ {n ^ {k}} \ right) = { \ mathsf {EXPSPACE}}}

În limbile obișnuite pot fi definite ca fiind . De fapt, avem chiar  : cel mai mic spațiu necesar pentru a recunoaște un limbaj non-rațional este și orice mașină Turing (deterministă sau nu) din spațiu recunoaște un limbaj rațional. REG=DSPLAVSE(O(1))=NUSPLAVSE(O(1)){\ displaystyle {\ mathsf {REG}} = {\ mathsf {DSPACE}} ({\ mathcal {O}} (1)) = {\ mathsf {NSPACE}} ({\ mathcal {O}} (1)) }REG=DSPLAVSE(o(Buturuga⁡Buturuga⁡nu))=NUSPLAVSE(o(Buturuga⁡Buturuga⁡nu)){\ displaystyle {\ mathsf {REG}} = {\ mathsf {DSPACE}} ({\ mathcal {o}} (\ log \ log n)) = {\ mathsf {NSPACE}} ({\ mathcal {o}} (\ log \ log n))}O(Buturuga⁡Buturuga⁡nu){\ displaystyle {\ mathcal {O}} (\ log \ log n)}o(Buturuga⁡Buturuga⁡nu){\ displaystyle o (\ log \ log n)}

Clasa de limbi contextuale poate fi definită ca fiind . VSSL=NUSPLAVSE(O(nu)){\ displaystyle {\ mathsf {CSL}} = {\ mathsf {NSPACE}} ({\ mathcal {O}} (n))}

Proprietăți

Ierarhia în spațiu

În mod informal, ierarhia în teorema spațiului indică faptul că a avea mai mult spațiu permite să se decidă mai multe probleme. Mai precis, pentru toate funcțiile și astfel încât și este construibil în spațiu , se verifică următoarea includere strictă: f{\ displaystyle f}g{\ displaystyle g}f=o(g){\ displaystyle f = o (g)}g{\ displaystyle g}

NUSPLAVSE(f(nu))⊊NUSPLAVSE(g(nu)){\ displaystyle {\ mathsf {NSPACE}} (f (n)) \ subsetneq {\ mathsf {NSPACE}} (g (n))}

Teorema Immerman-Szelepcsényi

Immerman-Szelepcsenyi teorema afirmă că clasele sunt N-Space închise de complementare  : pentru orice edificabil funcție în spațiu , cum ar fi  : f{\ displaystyle f}f(nu)≥Buturuga⁡nu{\ displaystyle f (n) \ geq \ log n}

NUSPLAVSE(f(nu))=vs.oNUSPLAVSE(f(nu)){\ displaystyle {\ mathsf {NSPACE}} (f (n)) = {\ mathsf {coNSPACE}} (f (n))}

În special ,. NUL=vs.oNUL{\ displaystyle {\ mathsf {NL}} = {\ mathsf {coNL}}}

Legături cu alte clase

Teorema Savitch leaga clasele de complexitate N-Space determinist de memorie dSpace următoarele incluziunile pentru orice funcție construirea de spațiu  : f{\ displaystyle f}f(nu)≥Buturuga⁡nu{\ displaystyle f (n) \ geq \ log n}

DSPLAVSE(f(nu))⊆NUSPLAVSE(f(nu))⊆DSPLAVSE(f(nu)2){\ displaystyle {\ mathsf {DSPACE}} (f (n)) \ subseteq {\ mathsf {NSPACE}} (f (n)) \ subseteq {\ mathsf {DSPACE}} \ left (f (n) ^ {2 } \ dreapta)}

O consecință este că PSPACE = NPSPACE .

În plus, NSPACE este legat de clasele de complexitate temporală DTIME și NTIME prin următoarele incluziuni, pentru orice funcție construibilă în spațiu: f{\ displaystyle f}

NUTEuME(f(nu))⊆DSPLAVSE(f(nu))⊆NUSPLAVSE(f(nu))⊆DTEuME(2O(f(nu))){\ displaystyle {\ mathsf {NTIME}} (f (n)) \ subseteq {\ mathsf {DSPACE}} (f (n)) \ subseteq {\ mathsf {NSPACE}} (f (n)) \ subseteq {\ mathsf {DTIME}} \ left (2 ^ {{\ mathcal {O}} (f (n))} \ right)}

Note și referințe

Referințe

1. (în) Andrzej Szepietowski , Mașini Turing cu spațiu Sublogaritmic , Springer Science + Business Media ,29 august 1994, 114  p. ( ISBN  978-3-540-58355-4 , citit online ) , p.  28

Bibliografie

• (ro) Sanjeev Arora și Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,20 aprilie 2009, 579  p. ( ISBN  978-0-521-42426-4 , citit online ). 
• Sylvain Perifel, algoritmice complexitate , Editions elipse ,22 aprilie 2014, 432  p. ( ISBN  978-2-729-88692-9 , citit online ).