About: EXPTIME

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