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

NEXPSPACE = k N NSPACE ( 2 n k )   . {\displaystyle {\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 {\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 2-EXPTIME = k N  DTIME  ( 2 2 n k ) {\displaystyle {\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, (ISBN 0-521-42426-7)
  • Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne)
v · m
Théorie de la complexité (informatique théorique)
Classes de complexité
(liste)
Classes classiques
Classes randomisées et quantiques
Autres
Classes de fonctions calculables
Hiérarchies
Familles de classes
Théorèmes et outils
Théorèmes structurels
Outils et réductions
Approches non-standard
  • icône décorative Portail de l'informatique théorique