|
In computational complexity theory, the complexity class 2-EXPTIME (sometimes called 2-EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2(2p(n))) time, where p(n) is a polynomial function of n.
In terms of DTIME,
- Failed to parse (Missing texvc executable; please see math/README to configure.): \mbox{2-EXPTIME} = \bigcup_{k \in \mathbb{N} } \mbox{ DTIME } \left( 2^{ 2^{n^k} } \right) .
We know
- P Failed to parse (Missing texvc executable; please see math/README to configure.): \subseteq
NP Failed to parse (Missing texvc executable; please see math/README to configure.): \subseteq
PSPACE Failed to parse (Missing texvc executable; please see math/README to configure.): \subseteq
EXPTIME Failed to parse (Missing texvc executable; please see math/README to configure.): \subseteq
NEXPTIME Failed to parse (Missing texvc executable; please see math/README to configure.): \subseteq
EXPSPACE Failed to parse (Missing texvc executable; please see math/README to configure.): \subseteq
2-EXPTIME.
2-EXPTIME can also be reformulated as the space class AEXPSPACE, the problems that can be solved by an alternating Turing machine in exponential space. This is one way to see that EXPSPACE Failed to parse (Missing texvc executable; please see math/README to configure.): \subseteq
2-EXPTIME, since an alternating Turing machine is at least as powerful as a deterministic Turing machine.[1]
2-EXPTIME is one class in a hierarchy of complexity classes with increasingly higher time bounds. The class 3-EXPTIME is defined similarly to 2-EXPTIME but with a triply-exponential time bound Failed to parse (Missing texvc executable; please see math/README to configure.): 2^{2^{2^n}}
. This can be generalized to higher and higher time bounds.
2-EXPTIME-complete problems
Generalizations of many fully observable games are EXPTIME-complete. These games can be viewed as particular instance of a class of transition systems defined in terms of a set of state variables and actions/events that change the values of the state variables, together with the question of whether a winning strategy exists.
A generalization of this class of fully observable problems to partially observable problems lifts the complexity from EXPTIME-complete to 2-EXPTIME-complete [2].
References
- ^ Papadimitriou (1994), section 20.1, corollary 3, page 495.
- ^ Jussi Rintanen (2004). "Complexity of Planning with Partial Observability". Proceedings of International Conference on Automated Planning and Scheduling: 345-354. AAAI Press.
| 
