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
[modifier | modifier le code ]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
[modifier | modifier le code ]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
[modifier | modifier le code ]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
[modifier | modifier le code ]Références
[modifier | modifier le code ]- ↑ (en) Andrzej Szepietowski, Turing Machines with Sublogarithmic Space, Springer Science+Business Media, , 114 p. (ISBN 978-3-540-58355-4, lire en ligne), p. 28
Bibliographie
[modifier | modifier le code ]- (en) Sanjeev Arora et Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, , 579 p. (ISBN 978-0-521-42426-4, lire en ligne). Ouvrage utilisé pour la rédaction de l'article
- Sylvain Perifel, Complexité algorithmique, Éditions Ellipses, , 432 p. (ISBN 978-2-729-88692-9, lire en ligne). Ouvrage utilisé pour la rédaction de l'article
| Classes de complexité (liste) |
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Théorèmes et outils |
|
||||||||||||
| Approches non-standard | |||||||||||||