Editing EXPTIME (section)

{{short description|Algorithmic complexity class}}
{{Redirect|EXP||Exp (disambiguation){{!}}Exp}}
<!--Basic definitions-->
In [[computational complexity theory]], the [[complexity class]] '''EXPTIME''' (sometimes called '''EXP''' or '''DEXPTIME''') is the [[Set (mathematics)|set]] of all [[decision problem]]s that are solvable by a [[deterministic Turing machine]]  in [[exponential time]], i.e., in [[big O notation|O]](2<sup>''p''(''n'')</sup>) time, where ''p''(''n'') is a polynomial function of ''n''.

EXPTIME is one intuitive class in an [[exponential hierarchy]] of complexity classes with increasingly more complex oracles or quantifier alternations. For example, the class [[2-EXPTIME]] is defined similarly to EXPTIME but with a [[Double exponential function|doubly exponential]] time bound. This can be generalized to higher and higher time bounds.

EXPTIME can also be reformulated as the space class APSPACE, the set of all problems that can be solved by an [[alternating Turing machine]] in polynomial space.

<!--Relationships to other classes-->
EXPTIME relates to the other basic time and space complexity classes in the following way: [[P (complexity)|P]] ⊆ [[NP (complexity)|NP]] ⊆ [[PSPACE]] ⊆ EXPTIME ⊆ [[NEXPTIME]] ⊆ [[EXPSPACE]]. Furthermore, by the [[time hierarchy theorem]] and the [[space hierarchy theorem]], it is known that P ⊊ EXPTIME, NP ⊊ NEXPTIME and PSPACE ⊊ EXPSPACE.