NSPACE

Les classes de complexité NL, NPSPACE et NEXPSPACE sont définies à partir de la famille NSPACE :

${\displaystyle {\mathsf {NL}}={\mathsf {NSPACE}}({\mathcal {O}}(\log n))}$

${\displaystyle {\mathsf {NPSPACE}}=\bigcup \limits _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})={\mathsf {PSPACE}}}$

${\displaystyle {\mathsf {NEXPSPACE}}=\bigcup \limits _{k\in \mathbb {N} }{\mathsf {NSPACE}}\left(2^{n^{k}}\right)={\mathsf {EXPSPACE}}}$

Les langages rationnels peuvent être définis comme ${\displaystyle {\mathsf {REG}}={\mathsf {DSPACE}}({\mathcal {O}}(1))={\mathsf {NSPACE}}({\mathcal {O}}(1))}$. En fait, on a même ${\displaystyle {\mathsf {REG}}={\mathsf {DSPACE}}({\mathcal {o}}(\log \log n))={\mathsf {NSPACE}}({\mathcal {o}}(\log \log n))}$ : le plus petit espace requis pour reconnaître un langage non rationnel est ${\displaystyle {\mathcal {O}}(\log \log n)}$, et toute machine de Turing (déterministe ou non) en espace ${\displaystyle o(\log \log n)}$ reconnaît un langage rationnel[1].

La classe des langages contextuels peut être définie comme ${\displaystyle {\mathsf {CSL}}={\mathsf {NSPACE}}({\mathcal {O}}(n))}$.

Le théorème de Savitch relie NSPACE aux classes de complexité en mémoire déterministe DSPACE par les inclusions suivantes, pour toute fonction ${\displaystyle f}$ constructible en espace telle que ${\displaystyle f(n)\geq \log n}$ :

${\displaystyle {\mathsf {DSPACE}}(f(n))\subseteq {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DSPACE}}\left(f(n)^{2}\right)}$

Une conséquence en est que PSPACE = NPSPACE.

Par ailleurs, NSPACE est relié aux classes de complexité en temps DTIME et NTIME par les inclusions suivantes, pour toute fonction ${\displaystyle f}$ constructible en espace :

${\displaystyle {\mathsf {NTIME}}(f(n))\subseteq {\mathsf {DSPACE}}(f(n))\subseteq {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DTIME}}\left(2^{{\mathcal {O}}(f(n))}\right)}$