2-EXPTIME

En informatique théorique, plus précisément en théorie de la complexité, la classe 2-EXPTIME est la classe des problèmes de décision décidés par une machine de Turing déterministe en temps doublement exponentiel, c'est-à-dire en temps O(22p(n)), où p(n) est un polynôme en la taille de l'entrée n.

2-EXPTIME est égale à la classe AEXPSPACE, la classe des problèmes décidés par une machine de Turing alternante en espace exponentiel[1].

Problèmes 2-EXPTIME complets

[modifier | modifier le code]

Des généralisations de problèmes avec observation totale à observation partielle passent de EXPTIME-complet à 2-EXPTIME-complet, par exemple le problème de planification avec actions non-déterministes et observation partielle est 2-EXPTIME-complet[2]. Le problème de synthèse de programmes réactifs à partir d'une spécification en logique temporelle linéaire est 2-EXPTIME-complet[3]. Le problème de satisfiabilité de la logique temporelle CTL* est 2-EXPTIME-complet[4]. Le problème de model checking (vérification de modèles) et le problème de satisfiabilité d'ATL* (alternating-time temporal logic, une logique pour raisonner sur des stratégies) est 2-EXPTIME-complet[5],[6].

Notes et références

[modifier | modifier le code]
  1. ↑ Christos Papadimitriou, Computational Complexity (1994), (ISBN 978-0-201-53082-7). Section 20.1, corollary 3, page 495.
  2. ↑ Jussi Rintanen, « Complexity of Planning with Partial Observability », AAAI Press,‎ , p. 345–354 (lire en ligne)
  3. ↑ (en) Amir Pnueli et Roni Rosner, « On the synthesis of an asynchronous reactive module », Automata, Languages and Programming, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ , p. 652–671 (ISBN 9783540513711, DOI 10.1007/BFb0035790, lire en ligne, consulté le )
  4. ↑ Christel Baier et Joost-Pieter Katoen, Principles of Model Checking (Representation and Mind Series), The MIT Press, , 975 p. (ISBN 978-0-262-02649-9 et 0-262-02649-X, lire en ligne)
  5. ↑ Rajeev Alur, Thomas A. Henzinger et Orna Kupferman, « Alternating-time Temporal Logic », J. ACM, vol. 49,‎ , p. 672–713 (ISSN 0004-5411, DOI 10.1145/585265.585270, lire en ligne, consulté le ).
  6. ↑ (en) Sven Schewe, « ATL* Satisfiability Is 2EXPTIME-Complete », Automata, Languages and Programming, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ , p. 373–385 (ISBN 9783540705826, DOI 10.1007/978-3-540-70583-3_31, lire en ligne, consulté le )