Loading AI tools
Da Wikipédia, a enciclopédia livre
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),
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),
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.