EXPTIME
EXPTIME（EXPとも）は、計算量理論において、チューリング機械で O(2"p"("n")) の時間で解ける全ての決定問題の集合である。なお、"p"("n") は "n" の多項式関数である。
DTIMEでは次のように表される。
以下の関係が知られている。
また、時間階層定理と領域階層定理により、次のようになる。
従って、包含関係の最初の3つのうち少なくとも1つが真部分集合の関係であり、後半3つのうち少なくとも1つが真部分集合の関係にある。ただし、どれがそうなのかは分かっていない。多くの研究者は上記の全てが真部分集合の関係であると考えている。また、P = NP であれば EXPTIME = NEXPTIME となることが分かっている。NEXPTIME は非決定性チューリング機械で指数関数時間で解ける問題のクラスである。
EXPTIME は空間（領域）のクラス APSPACE にも等しい。APSPACE は交替性チューリング機械で多項式領域で解ける問題のクラスである。交替性チューリング機械は決定性チューリング機械と少なくとも同程度に強力であるので、これによっても PSPACE formula_2 EXPTIME が示される。
EXPTIME は時間計算量に関する階層の一部となっている。2-EXPTIME クラスは EXPTIME と似ているが、二重指数時間 formula_11 かかる問題のクラスである。これを一般化していけば様々な時間計算量のクラスが定義される。