title: NSPACE
text: # NSPACE
  
  En théorie de la complexité, NSPACE désigne une famille de classes de complexité caractérisées par leur complexité en espace sur une machine de Turing non déterministe.
  
  Plus précisément, ${\mathsf {NSPACE}}(f(n))$ est la classe des problèmes de décision qui, pour une entrée de taille $n$, peuvent être décidés par une machine de Turing non déterministe fonctionnant en espace ${\mathcal {O}}(f(n))$.
  
  ## Définitions
  
  Les classes de complexité NL, NPSPACE et NEXPSPACE sont définies à partir de la famille NSPACE :
  
      ${\mathsf {NL}}={\mathsf {NSPACE}}({\mathcal {O}}(\log n))$
      ${\mathsf {NPSPACE}}=\bigcup \limits _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})={\mathsf {PSPACE}}$
      ${\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 ${\mathsf {REG}}={\mathsf {DSPACE}}({\mathcal {O}}(1))={\mathsf {NSPACE}}({\mathcal {O}}(1))$. En fait, on a même ${\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 ${\mathcal {O}}(\log \log n)$, et toute machine de Turing (déterministe ou non) en espace $o(\log \log n)$ reconnaît un langage rationnel.
  
  La classe des langages contextuels peut être définie comme ${\mathsf {CSL}}={\mathsf {NSPACE}}({\mathcal {O}}(n))$.
  
  ## Propriétés
  
  ### Hiérarchie en espace
  
  Informellement, le théorème de hiérarchie en espace indique que disposer de plus d'espace permet de décider davantage de problèmes. Plus précisément, pour toutes fonctions $f$ et $g$ telles que $f=o(g)$ et $g$ est constructible en espace, l'inclusion stricte suivante est vérifiée :
  
      ${\mathsf {NSPACE}}(f(n))\subsetneq {\mathsf {NSPACE}}(g(n))$
  
  ### Théorème d'Immerman-Szelepcsényi
  
  Le théorème d'Immerman-Szelepcsényi affirme que les classes NSPACE sont closes par complémentaire : pour toute fonction $f$ constructible en espace telle que $f(n)\geq \log n$ :
  
      ${\mathsf {NSPACE}}(f(n))={\mathsf {coNSPACE}}(f(n))$
  
  En particulier, ${\mathsf {NL}}={\mathsf {coNL}}$.
  
  ## Liens avec d'autres classes
  
  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 $f$ constructible en espace telle que $f(n)\geq \log n$ :
  
      ${\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 $f$ constructible en espace :
  
      ${\mathsf {NTIME}}(f(n))\subseteq {\mathsf {DSPACE}}(f(n))\subseteq {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DTIME}}\left(2^{{\mathcal {O}}(f(n))}\right)$
  