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 $\text{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 :

$\text{NEXPSPACE}=\bigcup _{k\in \mathbb{N}}\text{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 $\subseteq$ PSPACE $\subseteq$ EXPTIME $\subseteq$ NEXPSPACE.

D'après le Modèle:Lien, 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 $\text{2-EXPTIME}=\bigcup _{k\in \mathbb{N}}\text{ DTIME }\left(2^{2^{n^k}}\right)$).

Bibliographie

• Modèle:Computational Complexity (Arora et Barak)
• Modèle:Complexité algorithmique (Perifel)