Accueil🇫🇷Chercher

NSPACE

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

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

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

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

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

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

Références

  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

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.