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
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
- Christos Papadimitriou, Computational Complexity (1994), (ISBN 978-0-201-53082-7). Section 20.1, corollary 3, page 495.
- Jussi Rintanen, « Complexity of Planning with Partial Observability », AAAI Press,‎ , p. 345–354 (lire en ligne)
- (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 )
- 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)
- 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 ).
- (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 )