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, est la classe des problèmes de décision qui, pour une entrée de taille , peuvent être décidés par une machine de Turing déterministe fonctionnant en espace .

DéfinitionsModifier

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

 
 
 

Les langages rationnels peuvent être définis comme  . En fait, on a même   : le plus petit espace requis pour reconnaître un langage non rationnel est  , et toute machine de Turing en espace   reconnaît un langage rationnel[1].

Hiérarchie en espaceModifier

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   et   telles que   et   est constructible en espace, l'inclusion stricte suivante est vérifiée :

 

Liens avec d'autres classesModifier

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   constructible en espace telle que   :

 

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   constructible en espace :

 

Notes et référencesModifier

RéférencesModifier

  1. (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

BibliographieModifier