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.

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