Problèmes EXPSPACE-complete

J'essaie actuellement de trouver des problèmes EXPSPACE-complets (principalement pour trouver l'inspiration pour une réduction), et je suis surpris par le petit nombre de résultats à venir.

Jusqu'à présent, je les ai trouvés et j'ai du mal à élargir la liste:

• universalité (ou autres propriétés) des expressions régulières avec exponentiation.
• problèmes liés aux systèmes d'addition vectorielle
• jeux non observables (voir par exemple ce blog )
• un fragment de FO-LTL, dans Sur la complexité de calcul des fragments décidables des logiques temporelles linéaires du premier ordre

Connaissez-vous d'autres contextes où l'exhaustivité d'EXPSPACE apparaît naturellement?

L' extension de l'exemple souligné par Emil Jerabek dans les commentaires, problèmes COMPLETES se posent naturellement la géométrie algébrique sur tout. Cela a commencé (je pense) avec le problème de l'adhésion idéale ( Mayr – Meyer et Mayr ) et donc le calcul des bases de Gröbner. Ceci a ensuite été étendu au calcul des syzygies ( Bayer et Stillman ). De nombreux problèmes naturels en géométrie algébrique computationnelle finissent par être équivalents à l'un de ces problèmes. Voir aussi l' enquête Bayer – Mumford "Que peut-on calculer en géométrie algébrique?"$\mathsf{EXPSPACE}$

De nombreux problèmes qui sont PSPACE-complets deviennent EXPSPACE-complets lorsque l'entrée est donnée "succinctement", c'est-à-dire via un codage qui vous permet de décrire des entrées qui seraient normalement de taille exponentielle.

Voici un exemple sur les automates finis (de manière équivalente, sur les graphiques dirigés avec des bords étiquetés): décider si deux automates acceptent la même langue (ont le même ensemble de chemins étiquetés d'une origine à un nœud de destination) est PSPACE-complet. Si les automates (graphiques) sont donnés par des formules booléennes (les nœuds sont des évaluations v, v ', .. et qu'il existe des formules booléennes indiquant si va-> v' est un bord), le problème devient EXPSPACE-complete. NB: il existe de nombreuses autres façons de définir succinctement un grand graphe / automate, voir par exemple cet article .

L'exemple avec des expressions régulières correspond à ce modèle. L'introduction d'une notation ".. ^ 2" pour la mise au carré vous permet d'écrire des expressions régulières compactes qui seraient très grandes si vous étendez chaque "(foo) ^ 2" par "foo foo" et "((bar) ^ 2) ^ 2 "par" bar bar bar bar ". Naturellement, certains problèmes qui sont PSPACE-complet sans quadrature deviennent EXPSPACE-complet avec quadrature autorisé, voici la référence classique . [NB: D'autres exemples, comme les expressions régulières avec intersection ou avec des compléments, ne correspondent évidemment pas au modèle de nouvelle notation qui se développe en une entrée exponentiellement plus grande en notation standard.]

De même, un problème LOGSPACE-complete (par exemple, l'accessibilité dans les graphes dirigés) peut devenir EXPSPACE-complete si votre encodage succinct permet la description de graphes de taille doublement exponentielle.

Conclusion: vous pouvez facilement trouver de nouveaux problèmes, bien que peut-être artificiels, complets pour EXPSPACE, en considérant les problèmes classiques PSPACE ou LOGSPACE (dont vous trouverez beaucoup) et en permettant un codage compact / succinct / .. de l'entrée.

La planification temporelle avec des actions simultanées est terminée par EXPSPACE, comme indiqué dans

J. Rintanen, «Complexity of Concurrent Temporal Planning», Actes de la 17e Conférence internationale sur la planification et la planification automatisées, pp. 280-287, 2007

$A$$O$$o=(d,P_s,P_e,P_o,E_s,E_e)$

• $d\in\mathbb{N}$
• $P_s$$P_e$$P_o$$A$
• $E_s$$E_e$$A$

$I$$G$$I$$G$

$d$

La plupart des classes standard à partir de PSPACE (enfin, même pour NP, si vous le souhaitez) ont un problème de tuilage en tant que problème complet. De tels problèmes de carrelage ne sont pas si éloignés des problèmes complets naturels basés sur la machine de Turing, mais ils sont souvent très pratiques comme point de départ pour des réductions. En résumé, un problème de tuilage vous donne un ensemble de tuiles autorisées (c'est-à-dire: les types de tuiles à partir desquels vous pouvez utiliser autant de tuiles que vous le souhaitez) et détermine comment les combiner, souvent par un ensemble H de paires de tuiles et un ensemble V de types autorisés verticalement. De plus, une première tuile et une dernière tuile peuvent être données et, selon la version réelle, et combien de lignes et / ou colonnes le tuile devrait avoir. La question algorithmique est de savoir s'il existe un pavage correct, c'est-à-dire une affectation de positions aux tuiles, qui obéit à toutes les contraintes et a la tuile de départ en position inférieure gauche et la dernière tuile en position supérieure droite. (Il existe de nombreuses variantes quant aux définitions exactes).

Pour la classe en question, EXPSPACE, vous pouvez choisir entre (au moins) deux versions:

• pavage de couloir de largeur exponentielle, où un paramètre n est donné et la question est de savoir s'il existe un pavage avec 2 ^ n colonnes et un nombre quelconque de lignes
• jeu de tuiles exp-times-exp, où, étant donné n, le carrelage doit être de taille 2 ^ n fois 2 ^ n, où le premier objectif du joueur est d'atteindre un carrelage correct et le deuxième joueur essaie de l'empêcher.

Les articles à examiner sont - Bogdan S. Chlebus: "Domino-Tiling Games". J. Comput. Syst. Sci. 32 (3): 374-392 (1986) - Peter van Emde Boas: "The commodity of tilings", dans: Complexity, Logic and Recursion Theory, Lecture Notes in Pure and Applied Mathematics, Vol. 187, 1997, p. 331-363.

un exemple et une preuve sont donnés dans Introduction à la théorie des automates, aux langages et au calcul Hopcroft / Ullman Thm13.16 que tout algorithme non déterministe pour la théorie du premier ordre des réels avec addition est NExpTime-hard. il est donc vraisemblablement également NExpSpace-hard sauf si une percée théorique prouve qu'il peut être résolu "dans un espace plus restreint" mais bien sûr, cette question est similaire (presque identique?) à L =? P. (en d'autres termes, tous les problèmes sont également des candidats de base pour NExpSpace-hard, et s'ils existent, cela signifierait probablement une résolution révolutionnaire d'une séparation de classe de complexité longue ouverte.) la preuve vient de Fischer, Rabin 1974, «Complexité super exponentielle de l'arithmétique de Presburger», Complexité du calcul connus NExpTime-hard (R. Karp ed.). Actes du Symposium SIAM-AMS en mathématiques appliquées.