Mostrar código-fonte de NSPACE

Em [[Complexidade_computacional|teoria da complexidade computational]], a [[Classes_de_Complexidade|classe de complexidade]] '''NSPACE(''f''(''n''))''' é um conjunto de [[Problema_de_decisão|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:

* '''[[Linguagem_regular|REG]]''' = '''DSPACE'''(''O''(1)) = '''NSPACE'''(''O''(1)), onde '''REG''' é a classe  da [[Linguagem_regular|linguagens regulares]] (não-determinismo não adiciona poder a um espaço constante).
* '''[[Complexidade_NL|NL]]''' = '''NSPACE'''(''O''(log&nbsp;''n''))
* '''[[Linguagem_sensível_ao_contexto|CSL]]''' = '''NSPACE'''(''O''(''n'')), onde '''CSL''' é a classe das [[Linguagem sensível ao contexto|linguagens sensíveis ao contexto]].
* '''[[PSPACE]]''' = '''NPSPACE''' = <math>\bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(n^k)</math>
* '''[[EXPSPACE]]''' = '''NEXPSPACE''' = <math>\bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(2^{n^k})</math>

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''<sup>2</sup>(''n'')).

O [[Teorema de Immerman–Szelepcsényi]] diz que '''NSPACE'''(''s''(''n'')) é fechada sob a complementação para qualquer função {{nowrap|''s''(''n'') ≥ log ''n''.}}

'''NSPACE''' pode ser relacionada a [[DTIME]] tal como abaixo para qualquer [[função construtível]] ''s''(''n''),
:<math>\mbox{NSPACE}(s(n)) \subseteq \bigcup_{k \geq 1} \mbox{DTIME}(2^{k \cdot s(n)})</math>

== Bibliografia ==
* {{citar livro|autor = [[Michael Sipser]] |ano= 2006 |título= Introdução à Teoria da Computação |publicado= THOMSON | isbn = 0-534-95097-3 |capítulo= Sections 8.14&ndash |páginas=324–326 }}


{{Classes de complexidade}}
{{DEFAULTSORT:Nspace}}
[[Categoria:Classes de complexidade]]