NSPACE

Na teoria da complexidade , o NSPACE designa uma família de classes de complexidade caracterizadas por sua complexidade espacial em uma máquina de Turing não determinística .

Mais precisamente, é a classe de problemas de decisão que, para uma entrada de tamanho , pode ser decidida por uma máquina de Turing não determinística operando no espaço . NÃOSPNOVSE(f(não)){\ displaystyle {\ mathsf {NSPACE}} (f (n))}não{\ displaystyle n}O(f(não)){\ displaystyle {\ mathcal {O}} (f (n))}

Definições

As classes de complexidade NL , NPSPACE e NEXPSPACE são definidas a partir da família NSPACE:

NÃOeu=NÃOSPNOVSE(O(registro⁡não)){\ displaystyle {\ mathsf {NL}} = {\ mathsf {NSPACE}} ({\ mathcal {O}} (\ log n))}NÃOPSPNOVSE=⋃k∈NÃONÃOSPNOVSE(nãok)=PSPNOVSE{\ displaystyle {\ mathsf {NPSPACE}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {NSPACE}} (n ^ {k}) = {\ mathsf {PSPACE}}}NÃOEXPSPNOVSE=⋃k∈NÃONÃOSPNOVSE(2nãok)=EXPSPNOVSE{\ displaystyle {\ mathsf {NEXPSPACE}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {NSPACE}} \ left (2 ^ {n ^ {k}} \ right) = { \ mathsf {EXPSPACE}}}

As linguagens regulares podem ser definidas como . Na verdade, temos até  : o menor espaço necessário para reconhecer uma linguagem não racional é , e qualquer máquina de Turing (determinística ou não) no espaço reconhece uma linguagem racional. REG=DSPNOVSE(O(1))=NÃOSPNOVSE(O(1)){\ displaystyle {\ mathsf {REG}} = {\ mathsf {DSPACE}} ({\ mathcal {O}} (1)) = {\ mathsf {NSPACE}} ({\ mathcal {O}} (1)) }REG=DSPNOVSE(o(registro⁡registro⁡não))=NÃOSPNOVSE(o(registro⁡registro⁡não)){\ displaystyle {\ mathsf {REG}} = {\ mathsf {DSPACE}} ({\ mathcal {o}} (\ log \ log n)) = {\ mathsf {NSPACE}} ({\ mathcal {o}} (\ log \ log n))}O(registro⁡registro⁡não){\ displaystyle {\ mathcal {O}} (\ log \ log n)}o(registro⁡registro⁡não){\ displaystyle o (\ log \ log n)}

A classe de linguagens contextuais pode ser definida como . VSSeu=NÃOSPNOVSE(O(não)){\ displaystyle {\ mathsf {CSL}} = {\ mathsf {NSPACE}} ({\ mathcal {O}} (n))}

Propriedades

Hierarquia no espaço

Informalmente, o teorema da hierarquia no espaço indica que ter mais espaço permite que mais problemas sejam decididos. Mais precisamente, para todas as funções e tais que e sejam construtíveis no espaço , verifica-se a seguinte inclusão estrita: f{\ displaystyle f}g{\ displaystyle g}f=o(g){\ displaystyle f = o (g)}g{\ displaystyle g}

NÃOSPNOVSE(f(não))⊊NÃOSPNOVSE(g(não)){\ displaystyle {\ mathsf {NSPACE}} (f (n)) \ subsetneq {\ mathsf {NSPACE}} (g (n))}

Teorema de Immerman-Szelepcsényi

O teorema Immerman-Szelepcsényi afirma que as classes NSPACE são fechadas por complementares  : para qualquer função construtível no espaço, como  : f{\ displaystyle f}f(não)≥registro⁡não{\ displaystyle f (n) \ geq \ log n}

NÃOSPNOVSE(f(não))=vsoNÃOSPNOVSE(f(não)){\ displaystyle {\ mathsf {NSPACE}} (f (n)) = {\ mathsf {coNSPACE}} (f (n))}

Em particular ,. NÃOeu=vsoNÃOeu{\ displaystyle {\ mathsf {NL}} = {\ mathsf {coNL}}}

Links com outras classes

O teorema Savitch conecta NSPACE a memória determinística de classes de complexidade DSPACE as seguintes inclusões para qualquer espaço de construção de função como  : f{\ displaystyle f}f(não)≥registro⁡não{\ displaystyle f (n) \ geq \ log n}

DSPNOVSE(f(não))⊆NÃOSPNOVSE(f(não))⊆DSPNOVSE(f(não)2){\ displaystyle {\ mathsf {DSPACE}} (f (n)) \ subseteq {\ mathsf {NSPACE}} (f (n)) \ subseteq {\ mathsf {DSPACE}} \ left (f (n) ^ {2 } \ direito)}

Uma consequência é que PSPACE = NPSPACE .

Além disso, o NSPACE está vinculado às classes de complexidade de tempo DTIME e NTIME pelas seguintes inclusões, para qualquer função construtível no espaço: f{\ displaystyle f}

NÃOTeuME(f(não))⊆DSPNOVSE(f(não))⊆NÃOSPNOVSE(f(não))⊆DTeuME(2O(f(não))){\ 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)}

Notas e referências

Referências

1. (em) Andrzej Szepietowski , máquinas de Turing com espaço sublogarítmico , Springer Science + Business Media ,29 de agosto de 1994, 114  p. ( ISBN  978-3-540-58355-4 , leitura online ) , p.  28

Bibliografia

• (pt) Sanjeev Arora e Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,20 de abril de 2009, 579  p. ( ISBN  978-0-521-42426-4 , leia online ). 
• Sylvain Perifel, complexidade algorítmica , Éditions Ellipses ,22 de abril de 2014, 432  p. ( ISBN  978-2-729-88692-9 , leia online ).