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 l'ensemble de tous les problèmes qui peuvent être résolus par des machines de Turing non déterministes utilisant un espace pour une fonction en la taille de l'entrée , alors on peut définir NEXPSPACE par :

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 PSPACE EXPTIME 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 ).

Bibliographie

  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.