NEXPSPACE

NEXPSPACE est une classe de la théorie de la complexité. Elle regroupe l'ensemble des problèmes décidables en espace exponentiel par une machine de Turing non déterministe. Cette classe est égale à EXPSPACE d'après le théorème de Savitch.

Définition formelle

Si l'on appelle ${\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 $O(s(n))$ pour une fonction $s$ en la taille de l'entrée $n$, alors on peut définir NEXPSPACE par :

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

Liens avec les autres classes

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 $\scriptstyle \subseteq$ PSPACE $\scriptstyle \subseteq$ EXPTIME $\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 ${\mbox{2-EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{2^{n^{k}}}\right)$).

Bibliographie

• (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)