EXPSPACE

Un article de Wikipédia, l'encyclopédie libre.

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.

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

${\displaystyle {\mbox{EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{SPACE}}(2^{n^{k}})\ .}${\displaystyle {\mbox{EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{SPACE}}(2^{n^{k}})\ .}

Comme l'illustre l'image de droite, EXPSPACE contient la plupart des classes de complexité classiques. En particulier : NP ${\displaystyle \scriptstyle \subseteq }${\displaystyle \scriptstyle \subseteq } PSPACE ${\displaystyle \scriptstyle \subseteq }${\displaystyle \scriptstyle \subseteq } EXPTIME ${\displaystyle \scriptstyle \subseteq }${\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)}${\displaystyle {\mbox{2-EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{2^{n^{k}}}\right)}).

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.

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.

Les expressions rationnelles avec exponentiation (REX - Regular Expressions with Exponentiation) sur l'alphabet fini ${\displaystyle A}${\displaystyle A} sont les expressions obtenues à partir des lettres de A par les opérations suivantes :

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

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

1. ${\displaystyle L(\emptyset )=\emptyset }${\displaystyle L(\emptyset )=\emptyset }, ${\displaystyle L(\varepsilon )=\{\varepsilon \}}${\displaystyle L(\varepsilon )=\{\varepsilon \}}
2. ${\displaystyle L(a)=\{a\}}${\displaystyle L(a)=\{a\}} où ${\displaystyle a}${\displaystyle a} est une lettre de ${\displaystyle A}${\displaystyle A}
3. ${\displaystyle L(e+f)=L(e)\cup L(f)}${\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)\}}${\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)\}}${\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 }}${\displaystyle A^{\star }} l'ensemble des mots possibles sur l'alphabet ${\displaystyle A}${\displaystyle A}
6. ${\displaystyle \ L(e^{n})=\{x_{1}x_{2}\cdots x_{n}:x_{i}\in L(e)\}}${\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 \}}${\displaystyle L((a+b)^{3})=\{aaa,aab,aba,abb,\cdots \}}. Il est possible de remplacer toute opération d'exponentiation d'ordre ${\displaystyle n}${\displaystyle n} par ${\displaystyle n}${\displaystyle n} concaténations (par exemple ${\displaystyle (a+b)^{3}}${\displaystyle (a+b)^{3}} est similaire à ${\displaystyle (a+b)(a+b)(a+b)}${\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.

À 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 }\}}${\displaystyle ALL_{REX\uparrow }=\{e:e{\text{ est une REX telle que }}L(e)=A^{\star }\}}

Le problème ${\displaystyle ALL_{REX\uparrow }}${\displaystyle ALL_{REX\uparrow }} consiste ainsi à déterminer si une REX ${\displaystyle e}${\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 :

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.

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 }}${\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 }}).

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

Étant donné une REX ${\displaystyle e}${\displaystyle e} de taille ${\displaystyle n}${\displaystyle n}, l'algorithme suivant permet de déterminer en espace exponentiel si ${\displaystyle L(e)=A^{\star }}${\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)}}${\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)}${\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)}}}${\displaystyle 2^{O(N)}=2^{2^{O(n)}}} états.
4. ${\displaystyle e}${\displaystyle e} appartient à ${\displaystyle ALL_{REX\uparrow }}${\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})}${\displaystyle O(N^{2})} sur un graphe de taille ${\displaystyle 2^{O(N)}}${\displaystyle 2^{O(N)}}.

Puisqu'il n'est pas possible d'utiliser ${\displaystyle 2^{O(N)}=2^{2^{O(n)}}}${\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 }}${\displaystyle ALL_{REX\uparrow }} est EXPSPACE-hard

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

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

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

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

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

Condition 1. Au moment initial, la machine ${\displaystyle M}${\displaystyle M} est dans l'état ${\displaystyle q_{0}}${\displaystyle q_{0}} et ${\displaystyle w}${\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}${\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 }}${\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 }${\displaystyle C=x_{1}x_{2}\cdots x_{i}qx_{i+1}\cdots } la fenêtre est ${\displaystyle x_{i}qx_{i+1}}${\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}${\displaystyle abc} et ${\displaystyle def}${\displaystyle def} on note ${\displaystyle bad(abc,def)}${\displaystyle bad(abc,def)} s'il ne peut pas exister deux configurations successives ayant respectivement ${\displaystyle abc}${\displaystyle abc} et ${\displaystyle def}${\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 }}${\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}${\displaystyle M} finit dans l'état ${\displaystyle q_{reject}}${\displaystyle q_{reject}} en cas de calcul rejetant. Ainsi, pour que ${\displaystyle C_{t}}${\displaystyle C_{t}} ne soit pas une configuration finale rejetante, il suffit que ${\displaystyle w_{C}}${\displaystyle w_{C}} ne contienne pas ${\displaystyle q_{reject}}${\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 }}${\displaystyle R_{bad-reject}=\Delta _{-q_{reject}}^{\star }}.

Finalement, on note ${\displaystyle w_{R}=R_{bad-start}+R_{bad-window}+R_{bad-reject}}${\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\}}${\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 }}${\displaystyle w\in {\mathcal {L}}\Leftrightarrow L(w_{R})\in ALL_{REX\uparrow }}. Par ailleurs, ${\displaystyle w_{R}}${\displaystyle w_{R}} se construit bien en temps polynomial en ${\displaystyle n=|w|}${\displaystyle n=|w|} (${\displaystyle w_{R}}${\displaystyle w_{R}} est de taille ${\displaystyle O(n^{k})}${\displaystyle O(n^{k})}).

Le problème de satisfiabilité de certains fragments de la logique temporelle linéaire avec des quantifications du premier ordre est EXPSPACE-complet^[3] .

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

• (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)

• (en) La classe EXPSPACE sur le Complexity Zoo

• icône décorative Portail de l'informatique théorique

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=EXPSPACE&oldid=209184345 ».

Catégorie :

• Classe de complexité

Catégories cachées :

• Article contenant un appel à traduction en anglais
• Portail:Informatique théorique/Articles liés
• Portail:Informatique/Articles liés
• Portail:Mathématiques/Articles liés
• Portail:Sciences/Articles liés