DSPACE

En théorie de la complexité, DSPACE (ou SPACE) désigne une famille de classes de complexité caractérisées par leur complexité en espace sur une machine de Turing 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 déterministe fonctionnant en espace $𝒪(f(n))$.

Définitions

Les classes de complexité L, PSPACE et EXPSPACE sont définies à partir de la famille DSPACE :

$𝖫=𝖣𝖲𝖯𝖠𝖢𝖤(𝒪(\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))$. En fait, on a même $𝖱𝖤𝖦=𝖣𝖲𝖯𝖠𝖢𝖤(ℴ(\log \log n))$ : le plus petit espace requis pour reconnaître un langage non rationnel est $𝒪(\log \log n)$, et toute machine de Turing en espace $o(\log \log n)$ reconnaît un langage rationnel.

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))$

Liens avec d'autres classes

Le théorème de Savitch relie DSPACE aux classes de complexité en mémoire non déterministe NSPACE 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, DSPACE 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