NEXPSPACE — Wikipédia
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
[modifier | modifier le code]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
[modifier | modifier le code]![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e5/Hier.svg/200px-Hier.svg.png)
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
[modifier | modifier le code]- (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)