EXPTIME
ある EXPTIME の決定問題が EXPTIME完全であるとき、EXPTIME のあらゆる問題をその問題に多項式時間多対一還元できる。言い換えれば、ある問題の具体例を別の問題の具体例に多項式時間で変換するアルゴリズムがあり、その解が変わらない。EXPTIME完全の問題は EXPTIME の問題の中で最も難しいと考えられる。NP と P が一致するかどうかは分からないが、EXPTIME完全な問題が P に属さないことは分かっている。これは、EXPTIME完全な問題が多項式時間で解けないことを示すことで証明された。
計算可能性理論において、基本的な判定不能問題は決定性チューリング機械(DTM)がある入力を受理するかどうかの決定問題である。最も基本的なEXPTIME完全問題はこれを単純化したもので、あるDTMがある入力を最大 k ステップ以内に受理するかどうかの判定問題である。この問題は自明なシミュレーションが O(k) 時間かかり、入力 k が O(log k) ビットで符号化されることから EXPTIME となる。また、なぜ EXPTIME完全であると言えるかだが、大まかに言って、これを使ってある機械がEXPTIME問題を指数ステップで受理するかどうかを判定できるためであり、EXPTIME以上の時間は要しない。
従って、包含関係の最初の3つのうち少なくとも1つが真部分集合の関係であり、後半3つのうち少なくとも1つが真部分集合の関係にある。ただし、どれがそうなのかは分かっていない。多くの研究者は上記の全てが真部分集合の関係であると考えている。また、P = NP であれば EXPTIME = NEXPTIME となることが分かっている。NEXPTIME は非決定性チューリング機械で指数関数時間で解ける問題のクラスである。
EXPTIME は空間(領域)のクラス APSPACE にも等しい。APSPACE は交替性チューリング機械で多項式領域で解ける問題のクラスである。交替性チューリング機械は決定性チューリング機械と少なくとも同程度に強力であるので、これによっても PSPACE ⊆ {\displaystyle \subseteq } EXPTIME が示される。
EXPTIME は時間計算量に関する階層の一部となっている。2-EXPTIME クラスは EXPTIME と似ているが、二重指数時間 2 2 n {\displaystyle 2^{2^{n}}} かかる問題のクラスである。これを一般化していけば様々な時間計算量のクラスが定義される。