NSPACE

En teoria de la complexitat, la classe de complexitat NSPACE(f(n)) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en espai O(f(n)) i temps il·limitat. Es la contrapartida no determinista de la classe DSPACE.

Diverses classe de complexitat es defineixen en funció de DSPACE:

• REG = DSPACE(O(1)) = NSPACE(O(1)).
• NL = NSPACE(O(log n))
• CSL = NSPACE(O(n)), on CSL és la classe dels llenguatges sensibles al context
• PSPACE = NPSPACE = $\bigcup _{k\in \mathbb{N}}𝖭𝖲𝖯𝖠𝖢𝖤(n^k)$
• EXPSPACE = NEXPSPACE = $\bigcup _{k\in \mathbb{N}}𝖭𝖲𝖯𝖠𝖢𝖤(2^{n^k})$

Una generalització d'aquesta classe és ASPACE, que es defineix amb màquines de Turing alternants.

Relació amb d'altres classes

NSPACE és la contrapart no determinista de DSPACE, per la mateixa definició i pel teorema de Savitch es te:

$𝖣𝖲𝖯𝖠𝖢𝖤[s(n)]\subseteq 𝖭𝖲𝖯𝖠𝖢𝖤[s(n)]\subseteq 𝖣𝖲𝖯𝖠𝖢𝖤[(s(n){)}^2]$

NSPACE es pot fer servir per determinar la complexitat temporal d'una màquina de Turing determinista pel següent teorema:

Si un llenguatge L és dedicible en espai S(n) (on S(n) ≥ log n) per una màquina de Turing no determinista, llavors existeix una constant C tal que L és decidible en temps O(C^S(n)) per una màquina de Turing determinista.