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[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]

↑ 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

[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)

[1]

[2]

[3]

[4]

[5]

[6]