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.^[1][2]

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 = ${\displaystyle {\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})}}$
• EXPSPACE = NEXPSPACE = ${\displaystyle {\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(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:

${\displaystyle {\displaystyle {\mathsf {DSPACE}}[s(n)]\subseteq {\mathsf {NSPACE}}[s(n)]\subseteq {\mathsf {DSPACE}}[(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.^[3]

Referències