NSPACE

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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:

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),

\mbox{NSPACE}(s(n)) \subseteq \bigcup_{k \geq 1} \mbox{DTIME}(2^{k \cdot s(n)})

Referências[editar | editar código-fonte]

  • Página equivalente em inglês da wikipedia.
  • Michael Sipser. Introdução à Teoria da Computação. [S.l.]: THOMSON, 2006. 324–326 pp. ISBN 0-534-95097-3