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

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 $\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 :

1. L'opération $+$ ou $\cup$ (représente l'union)
2. L'opération $\cdot$ (représente le produit, le point est parfois omis)
3. L'opération $\_^{\star }$ (représente l'étoile de Kleene)
4. 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 :

1. $L(\emptyset )=\emptyset$, $L(\varepsilon )=\{\varepsilon \}$
2. $L(a)=\{a\}$ où $a$ est une lettre de $A$
3. $L(e+f)=L(e)\cup L(f)$
4. $\ L(e\cdot f)=\{x_{1}x_{2}:x_{1}\in L(e),x_{2}\in L(f)\}$
5. $\ 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$
6. $\ 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 }$ :

1. Remplacer les opérations d'exponentiation par des concaténations. On obtient une formule de taille $N=2^{O(n)}$.
2. Convertir cette formule (de manière naïve) en un automate non déterministe. Cette opération nécessite un espace $O(N)$.
3. Déterminiser l'automate précédant. Le nouvel automate peut avoir jusqu'à $2^{O(N)}=2^{2^{O(n)}}$ états.
4. $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 :

1. $C_{1}$ n'est pas une configuration initiale possible de $M$.
2. il existe 2 configurations successives $C_{i},C_{i+1}$ représentant une transition impossible.
3. $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.

Bibliographie

• (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7)
• Sylvain Perifel, Complexité algorithmique, Ellipses, 2014, 432 p. (ISBN 9782729886929, lire en ligne)

Liens externes

• (en) La classe EXPSPACE sur le Complexity Zoo