2-EXPTIME
# 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^{2p(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.

## 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^,.$

