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 ${\displaystyle {\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 ${\displaystyle O(s(n))}$ pour une fonction ${\displaystyle s}$ en la taille de l'entrée ${\displaystyle n}$, alors on définit EXPSPACE par :

${\displaystyle {\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 ${\displaystyle \scriptstyle \subseteq }$ PSPACE ${\displaystyle \scriptstyle \subseteq }$ EXPTIME ${\displaystyle \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 ${\displaystyle {\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^[1],[2]. 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 ${\displaystyle A}$ sont les expressions obtenues à partir des lettres de A par les opérations suivantes :

1. L'opération ${\displaystyle +}$ ou ${\displaystyle \cup }$ (représente l'union)
2. L'opération ${\displaystyle \cdot }$ (représente le produit, le point est parfois omis)
3. L'opération ${\displaystyle \_^{\star }}$ (représente l'étoile de Kleene)
4. L'opération ${\displaystyle \_^{n}}$ ou ${\displaystyle \uparrow n}$ (représente l'exponentiation d'ordre n)

À chaque REX ${\displaystyle e}$ est associé un langage rationnel ${\displaystyle L(e)}$ défini inductivement par :

1. ${\displaystyle L(\emptyset )=\emptyset }$, ${\displaystyle L(\varepsilon )=\{\varepsilon \}}$
2. ${\displaystyle L(a)=\{a\}}$ où ${\displaystyle a}$ est une lettre de ${\displaystyle A}$
3. ${\displaystyle L(e+f)=L(e)\cup L(f)}$
4. ${\displaystyle \ L(e\cdot f)=\{x_{1}x_{2}:x_{1}\in L(e),x_{2}\in L(f)\}}$
5. ${\displaystyle \ L(e^{\star })=\{x_{1}x_{2}\cdots x_{k}:k\geq 0,x_{i}\in L(e)\}}$ on note également ${\displaystyle A^{\star }}$ l'ensemble des mots possibles sur l'alphabet ${\displaystyle A}$
6. ${\displaystyle \ L(e^{n})=\{x_{1}x_{2}\cdots x_{n}:x_{i}\in L(e)\}}$

On a par exemple : ${\displaystyle L((a+b)^{3})=\{aaa,aab,aba,abb,\cdots \}}$. Il est possible de remplacer toute opération d'exponentiation d'ordre ${\displaystyle n}$ par ${\displaystyle n}$ concaténations (par exemple ${\displaystyle (a+b)^{3}}$ est similaire à ${\displaystyle (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 :

${\displaystyle ALL_{REX\uparrow }=\{e:e{\text{ est une REX telle que }}L(e)=A^{\star }\}}$

Le problème ${\displaystyle ALL_{REX\uparrow }}$ consiste ainsi à déterminer si une REX ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle ALL_{REX\uparrow }}$ à EXPSPACE, puis montrer que ce langage est EXPSPACE-hard (autrement dit, tout langage de EXPSPACE se réduit en temps polynomial à ${\displaystyle ALL_{REX\uparrow }}$).

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

Étant donné une REX ${\displaystyle e}$ de taille ${\displaystyle n}$, l'algorithme suivant permet de déterminer en espace exponentiel si ${\displaystyle L(e)=A^{\star }}$ :

1. Remplacer les opérations d'exponentiation par des concaténations. On obtient une formule de taille ${\displaystyle 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 ${\displaystyle O(N)}$.
3. Déterminiser l'automate précédant. Le nouvel automate peut avoir jusqu'à ${\displaystyle 2^{O(N)}=2^{2^{O(n)}}}$ états.
4. ${\displaystyle e}$ appartient à ${\displaystyle 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 ${\displaystyle O(N^{2})}$ sur un graphe de taille ${\displaystyle 2^{O(N)}}$.

Puisqu'il n'est pas possible d'utiliser ${\displaystyle 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.

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

Considérons un langage ${\displaystyle {\mathcal {L}}}$ reconnu par une machine de Turing déterministe ${\displaystyle M=(Q,\Gamma ,B,\Sigma ,q_{0},\delta ,F)}$ en espace ${\displaystyle 2^{n^{k}}}$. On va associer à tout mot ${\displaystyle w}$ une REX ${\displaystyle w_{R}}$ telle que ${\displaystyle w\in {\mathcal {L}}\Leftrightarrow L(w_{R})\in ALL_{REX\uparrow }}$. Plus précisément, on aura ${\displaystyle 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 ${\displaystyle M}$ au temps ${\displaystyle r}$ de son exécution est représenté par le mot ${\displaystyle C_{r}=x_{1}x_{2}\cdots x_{i}qx_{i+1}\cdots }$, où ${\displaystyle x_{j}}$ est le contenu de la case ${\displaystyle j}$ du ruban, ${\displaystyle q}$ l'état de la machine et ${\displaystyle x_{i+1}}$ le symbole placé sous la tête de lecture. Puisque ${\displaystyle M}$ s'exécute en espace ${\displaystyle 2^{n^{k}}}$, on peut supposer que ${\displaystyle C}$ est de taille ${\displaystyle 2^{n^{k}}}$ (quitte à compléter par des symboles blancs ${\displaystyle B}$).

Un calcul de ${\displaystyle M}$ sur une entrée ${\displaystyle w}$ est alors représenté par le mot ${\displaystyle C_{1}\#C_{2}\#\dots \#C_{t}}$ où chaque ${\displaystyle C_{i}}$ est l'encodage de l'état de la machine au temps ${\displaystyle i}$ de son exécution.

Un calcul ${\displaystyle w_{C}=C_{1}\#C_{2}\#\dots \#C_{t}}$ de ${\displaystyle M}$ sur une entrée ${\displaystyle w}$ n'est pas rejetant s'il vérifie au moins une des 3 conditions suivantes :

1. ${\displaystyle C_{1}}$ n'est pas une configuration initiale possible de ${\displaystyle M}$.
2. il existe 2 configurations successives ${\displaystyle C_{i},C_{i+1}}$ représentant une transition impossible.
3. ${\displaystyle C_{t}}$ n'est pas une configuration finale rejetante.

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

Condition 1. Au moment initial, la machine ${\displaystyle M}$ est dans l'état ${\displaystyle q_{0}}$ et ${\displaystyle w}$ est écrit sur son ruban. Ainsi, la seule configuration initiale possible est : ${\displaystyle 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 : ${\displaystyle 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 ${\displaystyle C=x_{1}x_{2}\cdots x_{i}qx_{i+1}\cdots }$ la fenêtre est ${\displaystyle 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 ${\displaystyle abc}$ et ${\displaystyle def}$ on note ${\displaystyle bad(abc,def)}$ s'il ne peut pas exister deux configurations successives ayant respectivement ${\displaystyle abc}$ et ${\displaystyle 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 : ${\displaystyle 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 ${\displaystyle M}$ finit dans l'état ${\displaystyle q_{reject}}$ en cas de calcul rejetant. Ainsi, pour que ${\displaystyle C_{t}}$ ne soit pas une configuration finale rejetante, il suffit que ${\displaystyle w_{C}}$ ne contienne pas ${\displaystyle q_{reject}}$. L'expression rationnelle suivante génère ainsi l'ensemble des mots vérifiant la condition 3 : ${\displaystyle R_{bad-reject}=\Delta _{-q_{reject}}^{\star }}$.

Finalement, on note ${\displaystyle w_{R}=R_{bad-start}+R_{bad-window}+R_{bad-reject}}$. On a bien ${\displaystyle L(w_{R})=\{s:s{\text{ est un mot ne représentant pas un calcul rejetant de }}M{\text{ sur }}w\}}$ et donc ${\displaystyle w\in {\mathcal {L}}\Leftrightarrow L(w_{R})\in ALL_{REX\uparrow }}$. Par ailleurs, ${\displaystyle w_{R}}$ se construit bien en temps polynomial en ${\displaystyle n=|w|}$ (${\displaystyle w_{R}}$ est de taille ${\displaystyle 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^[3].

Problème d'accessibilité

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

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

Notes et références

1. (en) Chris Umans, Kevin Lee, « Computational Complexity, Lecture Notes 8 », 19 février 2010
2. Albert R. Meyer et Larry Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129.
3. I. Hodkinson, R. Kontchakov, A. Kurucz et F. Wolter, « On the computational complexity of decidable fragments of first-order linear temporal logics », 10th International Symposium on Temporal Representation and Reasoning, 2003 and Fourth International Conference on Temporal Logic. Proceedings,‎ 1^er juillet 2003, p. 91–98 (DOI 10.1109/TIME.2003.1214884, lire en ligne, consulté le 17 octobre 2016)
4. (en) Charles Rackoff, « The covering and boundedness problems for vector addition systems », Theoretical Computer Science, vol. 6, n^o 2,‎ 1^er janvier 1978, p. 223–231 (ISSN 0304-3975, DOI 10.1016/0304-3975(78)90036-1, lire en ligne, consulté le 19 mai 2022)

• Portail de l'informatique théorique