2-EXPTIME
Encyclopedia
In computational complexity theory
, the complexity class
2-EXPTIME (sometimes called 2-EXP) is the set of all decision problem
s solvable by a deterministic Turing machine in O
(22p(n)) time, where p(n) is a polynomial function of n.
In terms of DTIME
,
We know
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
2-EXPTIME, since an alternating Turing machine is at least as powerful as a deterministic Turing machine.
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
. This can be generalized to higher and higher time bounds.
A generalization of this class of fully observable problems to partially observable problems lifts the complexity from EXPTIME
-complete to 2-EXPTIME-complete.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
2-EXPTIME (sometimes called 2-EXP) is the set of all decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s solvable by a deterministic Turing machine in O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(22p(n)) time, where p(n) is a polynomial function of n.
In terms of DTIME
DTIME
In computational complexity theory, DTIME is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm...
,
We know
- PP (complexity)In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
NPNP (complexity)In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
PSPACEPSPACEIn computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
EXPTIMEEXPTIMEIn computational complexity theory, the complexity class EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n....
NEXPTIMENEXPTIMEIn computational complexity theory, the complexity class NEXPTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time O for some polynomial p, and unlimited space....
EXPSPACEEXPSPACEIn complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O space, where p is a polynomial function of n...
2-EXPTIME 
ELEMENTARY.
2-EXPTIME can also be reformulated as the space class AEXPSPACE, the problems that can be solved by an alternating Turing machine
Alternating Turing machine
In computational complexity theory, an alternating Turing machine is a non-deterministic Turing machine with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP...
in exponential space. This is one way to see that EXPSPACE
2-EXPTIME, since an alternating Turing machine is at least as powerful as a deterministic Turing machine.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
. 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
EXPTIME
In computational complexity theory, the complexity class EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n....
-complete to 2-EXPTIME-complete.