EXPTIME
EXPTIME(EXPとも)は、計算量理論において、チューリング機械で O(2) の時間で解ける全ての決定問題の集合である。なお、p(n) は n の多項式関数である。
DTIMEでは次のように表される。
EXPTIME = ⋃ k ∈ N DTIME ( 2 n k ) . {\displaystyle {\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{n^{k}}\right).}
以下の関係が知られている。
P ⊆ {\displaystyle \subseteq } NP ⊆ {\displaystyle \subseteq } PSPACE ⊆ {\displaystyle \subseteq } EXPTIME ⊆ {\displaystyle \subseteq } NEXPTIME ⊆ {\displaystyle \subseteq } EXPSPACE
また、時間階層定理と領域階層定理により、次のようになる。
P ⊊ {\displaystyle \subsetneq } EXPTIME かつ NP ⊊ {\displaystyle \subsetneq } NEXPTIME かつ PSPACE ⊊ {\displaystyle \subsetneq } EXPSPACE