NSPACE

Em teoria da complexidade computational, a classe de complexidade NSPACE(f(n)) é um conjunto de problemas de decisão que podem ser resolvido por uma máquina de Turing não-determinística usando espaço O(f(n)), e tempo ilimitado. É o equivalente não-determinístico da DSPACE.

Diversas classes de complexidade podem ser definidas em termos do NSPACE. Tais como:

• REG = DSPACE(O(1)) = NSPACE(O(1)), onde REG é a classe da linguagens regulares (não-determinismo não adiciona poder a um espaço constante).
• NL = NSPACE(O(log n))
• CSL = NSPACE(O(n)), onde CSL é a classe das linguagens sensíveis ao contexto.
• PSPACE = NPSPACE = $\bigcup _{k\in \mathbb{N}}\text{NSPACE}(n^k)$
• EXPSPACE = NEXPSPACE = $\bigcup _{k\in \mathbb{N}}\text{NSPACE}(2^{n^k})$

Os últimos dois resultados abaixo derivam do teorema de Savitch, este define que para qualquer função f(n) ≥ log(n),

NSPACE(f(n)) ⊆ DSPACE(f²(n)).

O Teorema de Immerman–Szelepcsényi diz que NSPACE(s(n)) é fechada sob a complementação para qualquer função Predefinição:Nowrap

NSPACE pode ser relacionada a DTIME tal como abaixo para qualquer função construtível s(n),

$\text{NSPACE}(s(n))\subseteq \bigcup _{k\ge 1}\text{DTIME}(2^{k\cdot s(n)})$

Bibliografia

• Predefinição:Citar livro

Predefinição:Classes de complexidade