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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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)[modifier | modifier le code]

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[modifier | modifier le code]

À 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[modifier | modifier le code]

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[modifier | modifier le code]

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é[modifier | modifier le code]

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

Bibliographie[modifier | modifier le code]

(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[modifier | modifier le code]

(en) La classe EXPSPACE sur le Complexity Zoo

Notes et références[modifier | modifier le code]

↑ (en) Chris Umans, Kevin Lee, « Computational Complexity, Lecture Notes 8 », 19 février 2010
↑ 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.
↑ 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)
↑ (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

[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)

[1]

[2]

[3]

[4]