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 = ⋃ k ∈ N NSPACE ( n k ) {\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(n^{k})} EXPSPACE = NEXPSPACE = ⋃ k ∈ N NSPACE ( 2 n k ) {\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{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(f2(n)). O Teorema de Immerman–Szelepcsényi diz que NSPACE(s(n)) é fechada sob a complementação para qualquer função s(n) ≥ log n. NSPACE pode ser relacionada a DTIME tal como abaixo para qualquer função construtível s(n), NSPACE ( s ( n ) ) ⊆ ⋃ k ≥ 1 DTIME ( 2 k ⋅ s ( n ) ) {\displaystyle {\mbox{NSPACE}}(s(n))\subseteq \bigcup _{k\geq 1}{\mbox{DTIME}}(2^{k\cdot s(n)})}