En théorie de la complexité, NSPACE désigne une famille de classes de complexité caractérisées par leur complexité en espace sur une machine de Turing non 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 non déterministe fonctionnant en espace .

Définitions

modifier

Les classes de complexité NL, NPSPACE et NEXPSPACE sont définies à partir de la famille NSPACE :

 
 
 

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 (déterministe ou non) en espace   reconnaît un langage rationnel[1].

La classe des langages contextuels peut être définie comme  .

Propriétés

modifier

Hiérarchie en espace

modifier

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 :

 

Théorème d'Immerman-Szelepcsényi

modifier

Le théorème d'Immerman-Szelepcsényi affirme que les classes NSPACE sont closes par complémentaire : pour toute fonction   constructible en espace telle que   :

 

En particulier,  .

Liens avec d'autres classes

modifier

Le théorème de Savitch relie NSPACE aux classes de complexité en mémoire déterministe DSPACE par les inclusions suivantes, pour toute fonction   constructible en espace telle que   :

 

Une conséquence en est que PSPACE = NPSPACE.

Par ailleurs, NSPACE 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érences

modifier

Références

modifier
  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

Bibliographie

modifier