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, ${\mathsf {NSPACE}}(f(n))$ {\displaystyle {\mathsf {NSPACE}}(f(n))} est la classe des problèmes de décision qui, pour une entrée de taille $n$ {\displaystyle n}, peuvent être décidés par une machine de Turing non déterministe fonctionnant en espace ${\mathcal {O}}(f(n))$ {\displaystyle {\mathcal {O}}(f(n))}.

Définitions

[modifier | modifier le code ]

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

{\mathsf {NL}}={\mathsf {NSPACE}}({\mathcal {O}}(\log n))

{\displaystyle {\mathsf {NL}}={\mathsf {NSPACE}}({\mathcal {O}}(\log n))}

{\mathsf {NPSPACE}}=\bigcup \limits _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})={\mathsf {PSPACE}}

{\displaystyle {\mathsf {NPSPACE}}=\bigcup \limits _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})={\mathsf {PSPACE}}}

{\mathsf {NEXPSPACE}}=\bigcup \limits _{k\in \mathbb {N} }{\mathsf {NSPACE}}\left(2^{n^{k}}\right)={\mathsf {EXPSPACE}}

{\displaystyle {\mathsf {NEXPSPACE}}=\bigcup \limits _{k\in \mathbb {N} }{\mathsf {NSPACE}}\left(2^{n^{k}}\right)={\mathsf {EXPSPACE}}}

Les langages rationnels peuvent être définis comme ${\mathsf {REG}}={\mathsf {DSPACE}}({\mathcal {O}}(1))={\mathsf {NSPACE}}({\mathcal {O}}(1))$ {\displaystyle {\mathsf {REG}}={\mathsf {DSPACE}}({\mathcal {O}}(1))={\mathsf {NSPACE}}({\mathcal {O}}(1))}. En fait, on a même ${\mathsf {REG}}={\mathsf {DSPACE}}({\mathcal {o}}(\log \log n))={\mathsf {NSPACE}}({\mathcal {o}}(\log \log n))$ {\displaystyle {\mathsf {REG}}={\mathsf {DSPACE}}({\mathcal {o}}(\log \log n))={\mathsf {NSPACE}}({\mathcal {o}}(\log \log n))} : le plus petit espace requis pour reconnaître un langage non rationnel est ${\mathcal {O}}(\log \log n)$ {\displaystyle {\mathcal {O}}(\log \log n)}, et toute machine de Turing (déterministe ou non) en espace $o(\log \log n)$ {\displaystyle o(\log \log n)} reconnaît un langage rationnel^[1].

La classe des langages contextuels peut être définie comme ${\mathsf {CSL}}={\mathsf {NSPACE}}({\mathcal {O}}(n))$ {\displaystyle {\mathsf {CSL}}={\mathsf {NSPACE}}({\mathcal {O}}(n))}.

Propriétés

[modifier | modifier le code ]

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 $f$ {\displaystyle f} et $g$ {\displaystyle g} telles que $f=o(g)$ {\displaystyle f=o(g)} et $g$ {\displaystyle g} est constructible en espace, l'inclusion stricte suivante est vérifiée :

{\mathsf {NSPACE}}(f(n))\subsetneq {\mathsf {NSPACE}}(g(n))

{\displaystyle {\mathsf {NSPACE}}(f(n))\subsetneq {\mathsf {NSPACE}}(g(n))}

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

[modifier | modifier le code ]

Le théorème d'Immerman-Szelepcsényi affirme que les classes NSPACE sont closes par complémentaire : pour toute fonction $f$ {\displaystyle f} constructible en espace telle que $f(n)\geq \log n$ {\displaystyle f(n)\geq \log n} :

{\mathsf {NSPACE}}(f(n))={\mathsf {coNSPACE}}(f(n))

{\displaystyle {\mathsf {NSPACE}}(f(n))={\mathsf {coNSPACE}}(f(n))}

En particulier, ${\mathsf {NL}}={\mathsf {coNL}}$ {\displaystyle {\mathsf {NL}}={\mathsf {coNL}}}.

Liens avec d'autres classes

[modifier | modifier le code ]

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 $f$ {\displaystyle f} constructible en espace telle que $f(n)\geq \log n$ {\displaystyle f(n)\geq \log n} :

{\mathsf {DSPACE}}(f(n))\subseteq {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DSPACE}}\left(f(n)^{2}\right)

{\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, NSPACE est relié aux classes de complexité en temps DTIME et NTIME par les inclusions suivantes, pour toute fonction $f$ {\displaystyle f} constructible en espace :

{\mathsf {NTIME}}(f(n))\subseteq {\mathsf {DSPACE}}(f(n))\subseteq {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DTIME}}\left(2^{{\mathcal {O}}(f(n))}\right)

{\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, 29 août 1994, 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, 20 avril 2009, 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, 22 avril 2014, 432 p. (ISBN 978-2-729-88692-9, lire en ligne). Ouvrage utilisé pour la rédaction de l'article

v · m

Théorie de la complexité (informatique théorique)

Classes de complexité
(liste)

Classes classiques	L NL P NP NP-complet co-NP co-NP-complet NP-facile PSPACE E EXPTIME NE NEXPTIME EXPSPACE
Classes randomisées et quantiques	RP ZPP BPP EQP BQP QMA IP Protocole Arthur-Merlin PP BPL RL
Autres	P/poly NC APX AC⁰ UP
Classes de fonctions calculables	#-P #-P-complet
Hiérarchies	Hiérarchie polynomiale PH Hiérarchie booléenne
Familles de classes	DTIME NTIME DSPACE NSPACE

Théorèmes et outils

Théorèmes structurels	Théorème de Savitch Théorème d'Immerman-Szelepcsényi Théorème PCP Théorème de Karp-Lipton Théorème de Sipser-Gács-Lautemann Théorème de Toda
Outils et réductions	Théorème d'accélération linéaire Théorème de Cook Réduction polynomiale Kernelisation

Approches non-standard

icône décorative Portail de l'informatique théorique

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=NSPACE&oldid=181769911 ».