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, $𝖭𝖲𝖯𝖠𝖢𝖤(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 $𝒪(f(n))$.

Définitions

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

$𝖭𝖫=𝖭𝖲𝖯𝖠𝖢𝖤(𝒪(\log n))$

$𝖭𝖯𝖲𝖯𝖠𝖢𝖤=\bigcup _{k\in \mathbb{N}}𝖭𝖲𝖯𝖠𝖢𝖤(n^k)=𝖯𝖲𝖯𝖠𝖢𝖤$

$𝖭𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤=\bigcup _{k\in \mathbb{N}}𝖭𝖲𝖯𝖠𝖢𝖤\left(2^{n^k}\right)=𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤$

Les langages rationnels peuvent être définis comme $𝖱𝖤𝖦=𝖣𝖲𝖯𝖠𝖢𝖤(𝒪(1))=𝖭𝖲𝖯𝖠𝖢𝖤(𝒪(1))$. En fait, on a même $𝖱𝖤𝖦=𝖣𝖲𝖯𝖠𝖢𝖤(ℴ(\log \log n))=𝖭𝖲𝖯𝖠𝖢𝖤(ℴ(\log \log n))$ : le plus petit espace requis pour reconnaître un langage non rationnel est $𝒪(\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 $𝖢𝖲𝖫=𝖭𝖲𝖯𝖠𝖢𝖤(𝒪(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 :

$𝖭𝖲𝖯𝖠𝖢𝖤(f(n))⊊𝖭𝖲𝖯𝖠𝖢𝖤(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)\ge \log n$ :

$𝖭𝖲𝖯𝖠𝖢𝖤(f(n))=𝖼𝗈𝖭𝖲𝖯𝖠𝖢𝖤(f(n))$

En particulier, $𝖭𝖫=𝖼𝗈𝖭𝖫$.

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)\ge \log n$ :

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

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 :

$𝖭𝖳𝖨𝖬𝖤(f(n))\subseteq 𝖣𝖲𝖯𝖠𝖢𝖤(f(n))\subseteq 𝖭𝖲𝖯𝖠𝖢𝖤(f(n))\subseteq 𝖣𝖳𝖨𝖬𝖤\left(2^{𝒪(f(n))}\right)$

Notes et références

Bibliographie

• Modèle:Ouvrage
• Modèle:Ouvrage