NEXPSPACE

Si l'on appelle ${\displaystyle {\mbox{NSPACE}}(s(n))}$ l'ensemble de tous les problèmes qui peuvent être résolus par des machines de Turing non déterministes utilisant un espace ${\displaystyle O(s(n))}$ pour une fonction ${\displaystyle s}$ en la taille de l'entrée ${\displaystyle n}$, alors on peut définir NEXPSPACE par :

${\displaystyle {\mbox{NEXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(2^{n^{k}})\ .}$

Diagramme d'inclusions de quelques classes de complexité. Les flèches indiquent l'inclusion.

Comme l'illustre l'image de droite, NEXPSPACE contient la plupart des classes de complexité classiques. En particulier :
NP ${\displaystyle \scriptstyle \subseteq }$ PSPACE ${\displaystyle \scriptstyle \subseteq }$ EXPTIME ${\displaystyle \scriptstyle \subseteq }$ NEXPSPACE.

D'après le théorème de hiérarchie en espace (en), PSPACE est strictement incluse dans NEXPSPACE.

D'après le théorème de Savitch, NEXPSPACE est égale à EXPSPACE.

NEXPSPACE est incluse dans 2-EXPTIME (définie par ${\displaystyle {\mbox{2-EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{2^{n^{k}}}\right)}$).

• (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7)
• Sylvain Perifel, Complexité algorithmique, Ellipses, 2014, 432 p. (ISBN 9782729886929, lire en ligne)

• Portail de l'informatique théorique