# EXPSPACE

En théorie de la complexité, EXPSPACE est la classe des problèmes décidables en espace exponentiel par une machine de Turing déterministe.

## Définition formelle

Si l'on appelle ${\mbox{SPACE}}(s(n))$ l'ensemble de tous les problèmes qui peuvent être résolus par des machines de Turing déterministes utilisant un espace $O(s(n))$ pour une fonction $s$ en la taille de l'entrée $n$, alors on définit EXPSPACE par :
${\mbox{EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{SPACE}}(2^{n^{k}})\ .$

## Liens avec les autres classes

Comme l'illustre l'image de droite, EXPSPACE contient la plupart des classes de complexité classiques. En particulier : NP $\scriptstyle \subseteq$ PSPACE $\scriptstyle \subseteq$ EXPTIME $\scriptstyle \subseteq$ EXPSPACE.
D'après le théorème de hiérarchie en espace (en), 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 à co-EXPSPACE.
EXPSPACE est incluse dans 2-EXPTIME (définie par ${\mbox{2-EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{2^{n^{k}}}\right)$).

## 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 consiste à déterminer si une expression rationnelle avec exponentiation génère l'ensemble des mots de l'alphabet sur lequel elle est définie$^,$. 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 $A$ sont les expressions obtenues à partir des lettres de A par les opérations suivantes :
* L'opération $+$ ou $\cup$ (représente l'union)
* L'opération $\cdot$ (représente le produit, le point est parfois omis)
* L'opération $\_^{\star }$ (représente l'étoile de Kleene)
* L'opération $\_^{n}$ ou $\uparrow n$ (représente l'exponentiation d'ordre n)
À chaque REX $e$ est associé un langage rationnel $L(e)$ défini inductivement par :
* $L(\emptyset )=\emptyset$, $L(\varepsilon )=\{\varepsilon \}$
* $L(a)=\{a\}$ où $a$ est une lettre de $A$
* $L(e+f)=L(e)\cup L(f)$
* $\ L(e\cdot f)=\{x_{1}x_{2}:x_{1}\in L(e),x_{2}\in L(f)\}$
* $\ L(e^{\star })=\{x_{1}x_{2}\cdots x_{k}:k\geq 0,x_{i}\in L(e)\}$ on note également $A^{\star }$ l'ensemble des mots possibles sur l'alphabet $A$
* $\ L(e^{n})=\{x_{1}x_{2}\cdots x_{n}:x_{i}\in L(e)\}$
On a par exemple : $L((a+b)^{3})=\{aaa,aab,aba,abb,\cdots \}$. Il est possible de remplacer toute opération d'exponentiation d'ordre $n$ par $n$ concaténations (par exemple $(a+b)^{3}$ est similaire à $(a+b)(a+b)(a+b)$). 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 :
$ALL_{REX\uparrow }=\{e:e{\text{ est une REX telle que }}L(e)=A^{\star }\}$
Le problème $ALL_{REX\uparrow }$ consiste ainsi à déterminer si une REX $e$ 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 $ALL_{REX\uparrow }$ 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 $ALL_{REX\uparrow }$ à EXPSPACE, puis montrer que ce langage est EXPSPACE-hard (autrement dit, tout langage de EXPSPACE se réduit en temps polynomial à $ALL_{REX\uparrow }$).

##### $ALL_{REX\uparrow }\in$ EXPSPACE

Étant donné une REX $e$ de taille $n$, l'algorithme suivant permet de déterminer en espace exponentiel si $L(e)=A^{\star }$ :
* Remplacer les opérations d'exponentiation par des concaténations. On obtient une formule de taille $N=2^{O(n)}$.
* Convertir cette formule (de manière naïve) en un automate non déterministe. Cette opération nécessite un espace $O(N)$.
* Déterminiser l'automate précédant. Le nouvel automate peut avoir jusqu'à $2^{O(N)}=2^{2^{O(n)}}$ états.
* $e$ appartient à $ALL_{REX\uparrow }$ 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 $O(N^{2})$ sur un graphe de taille $2^{O(N)}$.
Puisqu'il n'est pas possible d'utiliser $2^{O(N)}=2^{2^{O(n)}}$ 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.

##### $ALL_{REX\uparrow }$ est EXPSPACE-hard

Considérons un langage ${\mathcal {L}}$ reconnu par une machine de Turing déterministe $M=(Q,\Gamma ,B,\Sigma ,q_{0},\delta ,F)$ en espace $2^{n^{k}}$. On va associer à tout mot $w$ une REX $w_{R}$ telle que $w\in {\mathcal {L}}\Leftrightarrow L(w_{R})\in ALL_{REX\uparrow }$. Plus précisément, on aura $L(w_{R})=\{s:s{\text{ est un mot ne représentant pas un calcul rejetant de }}M{\text{ sur }}w\}$.
L'état de la machine $M$ au temps $r$ de son exécution est représenté par le mot $C_{r}=x_{1}x_{2}\cdots x_{i}qx_{i+1}\cdots$, où $x_{j}$ est le contenu de la case $j$ du ruban, $q$ l'état de la machine et $x_{i+1}$ le symbole placé sous la tête de lecture. Puisque $M$ s'exécute en espace $2^{n^{k}}$, on peut supposer que $C$ est de taille $2^{n^{k}}$ (quitte à compléter par des symboles blancs $B$).
Un calcul de $M$ sur une entrée $w$ est alors représenté par le mot $C_{1}\#C_{2}\#\dots \#C_{t}$ où chaque $C_{i}$ est l'encodage de l'état de la machine au temps $i$ de son exécution.
Un calcul $w_{C}=C_{1}\#C_{2}\#\dots \#C_{t}$ de $M$ sur une entrée $w$ n'est pas rejetant s'il vérifie au moins une des 3 conditions suivantes :
* $C_{1}$ n'est pas une configuration initiale possible de $M$.
* il existe 2 configurations successives $C_{i},C_{i+1}$ représentant une transition impossible.
* $C_{t}$ n'est pas une configuration finale rejetante.
Pour chacune de ces 3 conditions, on construit une expression rationnelle $e$ qui génère l'ensemble des mots vérifiant la condition (on note $\Delta =\Gamma \cup Q\cup \{\#\}$ et $\Delta _{-a}=\Delta \backslash \{a\}$).
Condition 1. Au moment initial, la machine $M$ est dans l'état $q_{0}$ et $w$ est écrit sur son ruban. Ainsi, la seule configuration initiale possible est : $q_{0}w_{1}\cdots w_{n}B\cdots B$. L'expression rationnelle suivante génère alors l'ensemble des mots vérifiant la condition 1 : $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 }$
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 $C=x_{1}x_{2}\cdots x_{i}qx_{i+1}\cdots$ la fenêtre est $x_{i}qx_{i+1}$). 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 $abc$ et $def$ on note $bad(abc,def)$ s'il ne peut pas exister deux configurations successives ayant respectivement $abc$ et $def$ pour fenêtres. On génère alors l'ensemble des mots vérifiant la condition 2 à l'aide de l'expression rationnelle suivante : $R_{bad-window}=\bigcup _{bad(abc,def)}\Delta ^{\star }abc\Delta ^{2^{n^{k}}-2}def\Delta ^{\star }$.
Condition 3. On suppose que la machine $M$ finit dans l'état $q_{reject}$ en cas de calcul rejetant. Ainsi, pour que $C_{t}$ ne soit pas une configuration finale rejetante, il suffit que $w_{C}$ ne contienne pas $q_{reject}$. L'expression rationnelle suivante génère ainsi l'ensemble des mots vérifiant la condition 3 : $R_{bad-reject}=\Delta _{-q_{reject}}^{\star }$.
Finalement, on note $w_{R}=R_{bad-start}+R_{bad-window}+R_{bad-reject}$. On a bien $L(w_{R})=\{s:s{\text{ est un mot ne représentant pas un calcul rejetant de }}M{\text{ sur }}w\}$ et donc $w\in {\mathcal {L}}\Leftrightarrow L(w_{R})\in ALL_{REX\uparrow }$. Par ailleurs, $w_{R}$ se construit bien en temps polynomial en $n=|w|$ ($w_{R}$ est de taille $O(n^{k})$).

### 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.

### Problème d'accessibilité

Le problème d'accessibilité dans les lossy VASS (vector addition systems with states) est EXPSPACE-complet.