Voir la source de EXPSPACE

En [[théorie de la complexité (informatique théorique)|théorie de la complexité]], '''EXPSPACE''' est la [[classe de complexité|classe]] des problèmes décidables en [[complexité en espace|espace]] exponentiel par une [[machine de Turing]] déterministe.

== Définition formelle ==

Si l'on appelle <math>\mbox{SPACE}(s(n))</math> l'ensemble de tous les problèmes qui peuvent être résolus par des [[machine de Turing|machines de Turing]] déterministes utilisant un espace <math>O(s(n))</math> pour une fonction <math>s</math> en la taille de l'entrée <math>n</math>, alors on définit EXPSPACE par :

<math>\mbox{EXPSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{SPACE}(2^{n^k}) \ . </math>

== Liens avec les autres classes ==

[[Image:hier.svg|200px|vignette|Diagramme d'inclusions de quelques classes de complexité. Les flèches indiquent l'inclusion.]]
Comme l'illustre l'image de droite, EXPSPACE contient la plupart des classes de complexité classiques. En particulier : [[NP (complexité)|NP]] <math>\scriptstyle\subseteq</math> [[PSPACE]] <math>\scriptstyle\subseteq</math> [[EXPTIME]] <math>\scriptstyle\subseteq</math> EXPSPACE.

D'après le {{Lien|langue=en|trad=Space hierarchy theorem|fr=théorème de hiérarchie en espace}}, [[PSPACE]] est strictement incluse dans EXPSPACE. Savoir si EXPTIME est un sous-ensemble strict de EXPSPACE ou non est une question ouverte.

D'après le [[théorème de Savitch]], EXPSPACE est égale à [[NEXPSPACE]].

D'après le [[théorème d'Immerman-Szelepcsényi]], EXPSPACE est égale à [[Complémentaire (complexité)|co-]]EXPSPACE.

EXPSPACE est incluse dans [[2-EXPTIME]] (définie par <math> \mbox{2-EXPTIME} = \bigcup_{k \in \mathbb{N} } \mbox{ DTIME } \left( 2^{ 2^{n^k} } \right) </math>).

== Problèmes EXPSPACE-complets ==

Un [[problème de décision]] est EXPSPACE-complet s'il est dans EXPSPACE et que tout problème de EXPSPACE s'y réduit en temps polynomial.

=== Problème de l'universalité d'un langage rationnel décrit par des expressions rationnelles avec exponentiation ===
Un exemple de problème EXSPACE-[[complet (complexité)|complet]] consiste à déterminer si une [[langage rationnel|expression rationnelle]] avec exponentiation génère l'ensemble des mots de l'alphabet sur lequel elle est définie<ref>{{lien web|lang=en |auteur = Chris Umans, Kevin Lee | url = http://www.cs.caltech.edu/~umans/cs21/lec18.pdf| date = February 19, 2010 | titre = Computational Complexity, Lecture Notes 8}}</ref>{{,}}<ref>[[Albert R. Meyer]] et [[Larry Stockmeyer]]. [http://people.csail.mit.edu/meyer/rsq.pdf The equivalence problem for regular expressions with squaring requires exponential space]. ''13th IEEE Symposium on Switching and Automata Theory'', Oct 1972, pp.125–129.</ref>. Si on ne dispose pas de l'exponentiation dans le langage des expressions rationnelles le problème devient PSPACE-complet. L'exponentiation permet d'exprimer certaines expressions de façon exponentiellement plus concise, et de passer de PSPACE-complet à EXPSPACE-complet. Ce résultat est démontré en détail ci-dessous.

==== Expression rationnelle avec exponentiation (REX) ====

Les expressions rationnelles avec exponentiation (REX - ''Regular Expressions with Exponentiation'') sur l'alphabet fini <math>A</math> sont les expressions obtenues à partir des lettres de A par les opérations suivantes :
# L'opération <math>+</math> ou <math>\cup</math> (représente l'union)
# L'opération <math>\cdot</math> (représente le produit, le point est parfois omis)
# L'opération <math>\_^\star</math> (représente l'[[étoile de Kleene]])
# L'opération <math>\_^n</math> ou <math>\uparrow n</math> (représente l'exponentiation d'ordre n)

À chaque REX <math>e</math> est associé un langage rationnel <math>L(e)</math> défini inductivement par :
# <math>L(\emptyset) = \emptyset</math>, <math>L(\varepsilon) = \{\varepsilon\}</math>
# <math>L(a) = \{a\}</math> où <math>a</math> est une lettre de <math>A</math>
# <math>L(e+f) = L(e)\cup L(f)</math>
# <math>\ L(e\cdot f) = \{x_1 x_2 : x_1 \in L(e) , x_2 \in L(f)\}</math>
# <math>\ L(e^\star) = \{x_1 x_2 \cdots x_k : k \geq 0 , x_i \in L(e)\}</math> on note également <math>A^\star</math> l'ensemble des mots possibles sur l'alphabet <math>A</math>
# <math>\ L(e^n) = \{x_1 x_2 \cdots x_n : x_i \in L(e)\}</math>

On a par exemple : <math>L((a+b)^3) = \{ aaa, aab, aba, abb, \cdots \}</math>.
Il est possible de remplacer toute opération d'exponentiation d'ordre <math>n</math> par <math>n</math> concaténations (par exemple <math>(a+b)^3</math> est similaire à <math>(a+b)(a+b)(a+b)</math>). Cependant, cette transformation peut accroître de façon exponentielle la taille de la formule. La concision de l'opération d'exponentiation participe à l'importante complexité spatiale du problème ci-dessous.

==== Langage des REX universelles ====

À partir de la définition précédente d'une REX, on considère le langage suivant :

<math>ALL_{REX\uparrow} = \{ e : e \text{ est une REX telle que } L(e) = A^\star \}</math>

Le problème <math>ALL_{REX\uparrow}</math> consiste ainsi à déterminer si une REX <math>e</math> donnée génère l'ensemble des mots finis possibles sur son alphabet (une telle REX est qualifiée d'''universelle''). Ce problème est EXPSPACE-complet :

{{Théorème| Le problème <math>ALL_{REX\uparrow}</math> est EXPSPACE-complet.}}

Ce théorème est toujours valable si on restreint l'exponentiation à l'ordre 2. Si l'étoile de Kleene est retirée, le problème devient [[NEXPTIME]]-complet.

==== Démonstration ====

La démonstration du théorème précédant s'effectue en 2 étapes. Il faut tout d'abord prouver l'appartenance de <math>ALL_{REX\uparrow}</math> à EXPSPACE, puis montrer que ce langage est EXPSPACE-hard (autrement dit, tout langage de EXPSPACE se réduit en temps polynomial à <math>ALL_{REX\uparrow}</math>).

;<math>ALL_{REX\uparrow} \in </math> EXPSPACE

Étant donné une REX <math>e</math> de taille <math>n</math>, l'algorithme suivant permet de déterminer en espace exponentiel si <math>L(e) = A^\star</math> :
# Remplacer les opérations d'exponentiation par des concaténations. On obtient une formule de taille <math>N = 2^{O(n)}</math>.
# Convertir cette formule (de manière naïve) en un automate non déterministe. Cette opération nécessite un espace <math>O(N)</math>.
# Déterminiser l'automate précédant. Le nouvel automate peut avoir jusqu'à <math>2^{O(N)} = 2^{2^{O(n)}}</math> états.
# <math>e</math> appartient à <math>ALL_{REX\uparrow}</math> si et seulement si aucun état rejetant n'est atteignable dans l'automate déterministe précédant. D'après le théorème de Savitch, ceci se vérifie en espace <math>O(N^2)</math> sur un graphe de taille <math>2^{O(N)}</math>.

Puisqu'il n'est pas possible d'utiliser <math>2^{O(N)} = 2^{2^{O(n)}}</math> espace, l'automate déterministe n'est pas construit à l'étape 3 ci-dessus. À la place, il est recalculé au fur et à mesure de son parcours lors de l'étape 4.

;<math>ALL_{REX\uparrow}</math> est EXPSPACE-hard

Considérons un langage <math>\mathcal{L}</math> reconnu par une [[Machine de Turing#Définition formelle|machine de Turing déterministe]] <math>M = (Q,\Gamma, B, \Sigma, q_0, \delta, F)</math> en espace <math>2^{n^k}</math>. On va associer à tout mot <math>w</math> une REX <math>w_R</math> telle que <math>w \in \mathcal{L} \Leftrightarrow L(w_R) \in ALL_{REX\uparrow}</math>. Plus précisément, on aura <math>L(w_R) = \{ s : s \text{ est un mot ne représentant pas un calcul rejetant de } M \text{ sur } w\}</math>.

L'état de la machine <math>M</math> au temps <math>r</math> de son exécution est représenté par le mot <math>C_r = x_1 x_2 \cdots x_i q x_{i+1} \cdots</math>, où <math>x_j</math> est le contenu de la case <math>j</math> du ruban, <math>q</math> l'état de la machine et <math>x_{i+1}</math> le symbole placé sous la tête de lecture. Puisque <math>M</math> s'exécute en espace <math>2^{n^k}</math>, on peut supposer que <math>C</math> est de taille <math>2^{n^k}</math> (quitte à compléter par des symboles blancs <math>B</math>).

Un calcul de <math>M</math> sur une entrée <math>w</math> est alors représenté par le mot <math>C_1 \# C_2 \# \dots \# C_t</math> où chaque <math>C_i</math> est l'encodage de l'état de la machine au temps <math>i</math> de son exécution.

Un calcul <math>w_C = C_1 \# C_2 \# \dots \# C_t</math> de <math>M</math> sur une entrée <math>w</math> n'est pas rejetant s'il vérifie au moins une des 3 conditions suivantes :
# <math>C_1</math> n'est pas une configuration initiale possible de <math>M</math>.
# il existe 2 configurations successives <math>C_i, C_{i+1}</math> représentant une transition impossible.
# <math>C_t</math> n'est pas une configuration finale rejetante.

Pour chacune de ces 3 conditions, on construit une expression rationnelle <math>e</math> qui génère l'ensemble des mots vérifiant la condition (on note <math>\Delta = \Gamma \cup  Q \cup \{ \# \}</math> et <math>\Delta_{-a} = \Delta \backslash \{a\}</math>).

''Condition 1.'' Au moment initial, la machine <math>M</math> est dans l'état <math>q_0</math> et <math>w</math> est écrit sur son ruban. Ainsi, la seule configuration initiale possible est : <math>q_0 w_1 \cdots w_n B \cdots B</math>. L'expression rationnelle suivante génère alors l'ensemble des mots vérifiant la condition 1 :
<math>R_{bad-start} = \Delta_{-q_0} \Delta^\star + \Delta^1 \Delta_{-w_1} \Delta^\star + \Delta^2 \Delta_{-w_2} \Delta^\star + \cdots + \Delta^{n+1}(\Delta + \varepsilon)^{2^{n^k}-n-2} \Delta_{-B} \Delta^\star + \Delta^{2^{n^k}} \Delta_{-\#} \Delta^\star </math>

''Condition 2.'' Afin de savoir si une transition est valide ou non, il suffit d'étudier pour chaque paire de configurations successives des fenêtres de taille 3 centrées sur l'état courant (par exemple, pour la configuration <math>C = x_1 x_2 \cdots x_i q x_{i+1} \cdots</math> la fenêtre est <math>x_i q x_{i+1}</math>). En effet, les autres lettres de la configuration ne sont pas censées évoluer après seulement un pas de calcul. Pour deux fenêtres <math>abc</math> et <math>def</math> on note <math>bad(abc,def)</math> s'il ne peut pas exister deux configurations successives ayant respectivement <math>abc</math> et <math>def</math> pour fenêtres. On génère alors l'ensemble des mots vérifiant la condition 2 à l'aide de l'expression rationnelle suivante : <math>R_{bad-window} = \bigcup_{bad(abc,def)} \Delta^{\star} abc \Delta^{2^{n^k}-2} def \Delta^\star</math>.

''Condition 3.'' On suppose que la machine <math>M</math> finit dans l'état <math>q_{reject}</math> en cas de calcul rejetant. Ainsi, pour que <math>C_t</math> ne soit pas une configuration finale rejetante, il suffit que <math>w_C</math> ne contienne pas <math>q_{reject}</math>. L'expression rationnelle suivante génère ainsi l'ensemble des mots vérifiant la condition 3 : <math>R_{bad-reject} = \Delta^{\star}_{-q_{reject}}</math>.

Finalement, on note <math>w_R = R_{bad-start} + R_{bad-window} + R_{bad-reject}</math>. On a bien <math>L(w_R) = \{ s : s \text{ est un mot ne représentant pas un calcul rejetant de } M \text{ sur } w\}</math> et donc <math>w \in \mathcal{L} \Leftrightarrow L(w_R) \in ALL_{REX\uparrow}</math>. Par ailleurs, <math>w_R</math> se construit bien en temps polynomial en <math>n = |w|</math> (<math>w_R</math> est de taille <math>O(n^k)</math>).

=== En logique ===
Le problème de satisfiabilité de certains fragments de la [[logique temporelle]] linéaire avec des quantifications du premier ordre est EXPSPACE-complet<ref>{{Article|prénom1=I.|nom1=Hodkinson|prénom2=R.|nom2=Kontchakov|prénom3=A.|nom3=Kurucz|prénom4=F.|nom4=Wolter|titre=On the computational complexity of decidable fragments of first-order linear temporal logics|périodique=10th International Symposium on Temporal Representation and Reasoning, 2003 and Fourth International Conference on Temporal Logic. Proceedings|date=2003-07-01|doi=10.1109/TIME.2003.1214884|lire en ligne=http://ieeexplore.ieee.org/document/1214884/?reload=true|consulté le=2016-10-17|pages=91–98}}</ref>.

=== Problème d'accessibilité ===
Le [[problème d'accessibilité]] dans les lossy VASS (vector addition systems with states) est EXPSPACE-complet<ref>{{Article|langue=en|prénom1=Charles|nom1=Rackoff|titre=The covering and boundedness problems for vector addition systems|périodique=Theoretical Computer Science|volume=6|numéro=2|date=1978-01-01|issn=0304-3975|doi=10.1016/0304-3975(78)90036-1|lire en ligne=https://www.sciencedirect.com/science/article/pii/0304397578900361|consulté le=2022-05-19|pages=223–231}}</ref>.

== Bibliographie ==
* {{Computational Complexity (Arora et Barak)}}
* {{Complexité algorithmique (Perifel)}}

== Liens externes ==
* {{Complexity Zoo|fin=E#expspace|nom=EXPSPACE}}

== Notes et références ==
{{Références}}

{{Palette|Théorie de la complexité}}

{{Portail|Informatique théorique}}

[[Catégorie:Classe de complexité]]