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(2^{2^p(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,‎ 2004, 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,‎ 11 juillet 1989, p. 652–671 (ISBN 9783540513711, DOI 10.1007/BFb0035790, lire en ligne, consulté le 7 février 2018)
Christel Baier et Joost-Pieter Katoen, Principles of Model Checking (Representation and Mind Series), The MIT Press, 1^er janvier 2008, 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,‎ 1^er septembre 2002, p. 672–713 (ISSN 0004-5411, DOI 10.1145/585265.585270, lire en ligne, consulté le 1^er avril 2016).
(en) Sven Schewe, « ATL* Satisfiability Is 2EXPTIME-Complete », Automata, Languages and Programming, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 7 juillet 2008, p. 373–385 (ISBN 9783540705826, DOI 10.1007/978-3-540-70583-3_31, lire en ligne, consulté le 8 février 2018)

Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[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,‎ 2004, 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,‎ 11 juillet 1989, p. 652–671 (ISBN 9783540513711, DOI 10.1007/BFb0035790, lire en ligne, consulté le 7 février 2018)

[:02-4] Christel Baier et Joost-Pieter Katoen, Principles of Model Checking (Representation and Mind Series), The MIT Press, 1^er janvier 2008, 975 p. (ISBN 978-0-262-02649-9 et 0-262-02649-X, lire en ligne)

[:0-5] Rajeev Alur, Thomas A. Henzinger et Orna Kupferman, « Alternating-time Temporal Logic », J. ACM, vol. 49,‎ 1^er septembre 2002, p. 672–713 (ISSN 0004-5411, DOI 10.1145/585265.585270, lire en ligne, consulté le 1^er avril 2016).

[6] (en) Sven Schewe, « ATL* Satisfiability Is 2EXPTIME-Complete », Automata, Languages and Programming, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 7 juillet 2008, p. 373–385 (ISBN 9783540705826, DOI 10.1007/978-3-540-70583-3_31, lire en ligne, consulté le 8 février 2018)