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, ${\displaystyle {\mathsf {DSPACE}}(f(n))}$ est la classe des problèmes de décision qui, pour une entrée de taille ${\displaystyle n}$, peuvent être décidés par une machine de Turing déterministe fonctionnant en espace ${\displaystyle {\mathcal {O}}(f(n))}$.

Définitions

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

${\displaystyle {\mathsf {L}}={\mathsf {DSPACE}}({\mathcal {O}}(\log n))}$

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

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

Les langages rationnels peuvent être définis comme ${\displaystyle {\mathsf {REG}}={\mathsf {DSPACE}}({\mathcal {O}}(1))}$. En fait, on a même ${\displaystyle {\mathsf {REG}}={\mathsf {DSPACE}}({\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 en espace ${\displaystyle o(\log \log n)}$ reconnaît un langage rationnel^[1].

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 ${\displaystyle f}$ et ${\displaystyle g}$ telles que ${\displaystyle f=o(g)}$ et ${\displaystyle g}$ est constructible en espace, l'inclusion stricte suivante est vérifiée :

${\displaystyle {\mathsf {DSPACE}}(f(n))\subsetneq {\mathsf {DSPACE}}(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 ${\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, DSPACE 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)}$

Notes et références

Références

Bibliographie

• (en) Sanjeev Arora et Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 20 avril 2009, 579 p. (ISBN 978-0-521-42426-4, lire en ligne). 
• Sylvain Perifel, Complexité algorithmique, Éditions Ellipses, 22 avril 2014, 432 p. (ISBN 978-2-729-88692-9, lire en ligne). 

• Portail de l'informatique théorique