EXPSPACE

classe de complexité

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

Si l'on appelle l'ensemble de tous les problèmes qui peuvent être résolus par des machines de Turing déterministes utilisant un espace pour une fonction en la taille de l'entrée , alors on définit EXPSPACE par :

Liens avec les autres classes

modifier
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 PSPACE EXPTIME 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 ).

Problèmes EXPSPACE-complets

modifier

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

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

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

  1. L'opération ou (représente l'union)
  2. L'opération (représente le produit, le point est parfois omis)
  3. L'opération (représente l'étoile de Kleene)
  4. L'opération ou (représente l'exponentiation d'ordre n)

À chaque REX est associé un langage rationnel défini inductivement par :

  1. ,
  2. est une lettre de
  3. on note également l'ensemble des mots possibles sur l'alphabet

On a par exemple : . Il est possible de remplacer toute opération d'exponentiation d'ordre par concaténations (par exemple est similaire à ). 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

À partir de la définition précédente d'une REX, on considère le langage suivant :

Le problème consiste ainsi à déterminer si une REX 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 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

La démonstration du théorème précédant s'effectue en 2 étapes. Il faut tout d'abord prouver l'appartenance de à EXPSPACE, puis montrer que ce langage est EXPSPACE-hard (autrement dit, tout langage de EXPSPACE se réduit en temps polynomial à ).

EXPSPACE

Étant donné une REX de taille , l'algorithme suivant permet de déterminer en espace exponentiel si  :

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

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

est EXPSPACE-hard

Considérons un langage reconnu par une machine de Turing déterministe en espace . On va associer à tout mot une REX telle que . Plus précisément, on aura .

L'état de la machine au temps de son exécution est représenté par le mot , où est le contenu de la case du ruban, l'état de la machine et le symbole placé sous la tête de lecture. Puisque s'exécute en espace , on peut supposer que est de taille (quitte à compléter par des symboles blancs ).

Un calcul de sur une entrée est alors représenté par le mot où chaque est l'encodage de l'état de la machine au temps de son exécution.

Un calcul de sur une entrée n'est pas rejetant s'il vérifie au moins une des 3 conditions suivantes :

  1. n'est pas une configuration initiale possible de .
  2. il existe 2 configurations successives représentant une transition impossible.
  3. n'est pas une configuration finale rejetante.

Pour chacune de ces 3 conditions, on construit une expression rationnelle qui génère l'ensemble des mots vérifiant la condition (on note et ).

Condition 1. Au moment initial, la machine est dans l'état et est écrit sur son ruban. Ainsi, la seule configuration initiale possible est : . L'expression rationnelle suivante génère alors l'ensemble des mots vérifiant la condition 1 :

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 la fenêtre est ). 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 et on note s'il ne peut pas exister deux configurations successives ayant respectivement et pour fenêtres. On génère alors l'ensemble des mots vérifiant la condition 2 à l'aide de l'expression rationnelle suivante : .

Condition 3. On suppose que la machine finit dans l'état en cas de calcul rejetant. Ainsi, pour que ne soit pas une configuration finale rejetante, il suffit que ne contienne pas . L'expression rationnelle suivante génère ainsi l'ensemble des mots vérifiant la condition 3 : .

Finalement, on note . On a bien et donc . Par ailleurs, se construit bien en temps polynomial en ( est de taille ).

En logique

modifier

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

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

Bibliographie

modifier

Liens externes

modifier

Notes et références

modifier
  1. (en) Chris Umans, Kevin Lee, « Computational Complexity, Lecture Notes 8 »,
  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,‎ , p. 91–98 (DOI 10.1109/TIME.2003.1214884, lire en ligne, consulté le )
  4. (en) Charles Rackoff, « The covering and boundedness problems for vector addition systems », Theoretical Computer Science, vol. 6, no 2,‎ , p. 223–231 (ISSN 0304-3975, DOI 10.1016/0304-3975(78)90036-1, lire en ligne, consulté le )