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 exponentielChristos Papadimitriou, Computational Complexity (1994), . Section 20.1, corollary 3, page 495..
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. Le problème de synthèse de programmes réactifs à partir d'une spécification en logique temporelle linéaire est 2-EXPTIME-complet. Le problème de satisfiabilité de la logique temporelle CTL* est 2-EXPTIME-complet. 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..
Notes et références
Catégorie:Classe de complexité