有効期限

計算複雑性理論において、計算複雑性クラス EXPTIME ( EXPまたはDEXPTIMEと呼ばれることもある) は、決定論的チューリングマシンによって指数時間、つまりO (2 ^{p ( n )} ) 時間 で解決可能なすべての決定問題の集合であり、ここでp ( n ) はnの多項式関数である。

EXPTIME は、ますます複雑になるオラクルや量指定子の交替を伴う複雑性クラスの指数的階層における 1 つの直感的なクラスです。たとえば、クラス2-EXPTIME はEXPTIME と同様に定義されますが、二重指数の時間境界を持ちます。これは、より高い時間境界に一般化できます。

EXPTIME は、多項式空間内の交代チューリング マシンによって解決できるすべての問題の集合である空間クラス APSPACE として再定式化することもできます。

EXPTIME は、他の基本的な時間および空間計算量クラスと次のように関連しています: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE。さらに、時間階層定理と空間階層定理により、P ⊊ EXPTIME、NP ⊊ NEXPTIME、PSPACE ⊊ EXPSPACE であることが分かっています。

DTIMEに関しては、

${\displaystyle {\mathsf {EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{n^{k}}\right).}$

知られているのは

また、時間階層定理と空間階層定理によれば、

上記の式では、記号 ⊆ は「 のサブセットである」ことを意味し、記号 ⊊ は「 の厳密なサブセットである」ことを意味します。

したがって、最初の 3 つの包含のうち少なくとも 1 つと最後の 3 つの包含のうち少なくとも 1 つは適切でなければなりませんが、どれが適切であるかはわかりません。また、P = NPの場合、 EXPTIME = NEXPTIMEであり、非決定性チューリングマシンによって指数時間で解ける問題のクラスであることもわかっています。^[1]より正確には、PにないNPのスパース言語が存在する場合のみ、E ≠ NE です。^[2]

EXPTIMEは、多項式空間内の交代チューリングマシンによって解決できるすべての問題の集合である空間クラスAPSPACEとして再定式化できます。これは、交代チューリングマシンが決定論的チューリングマシンと少なくとも同じくらい強力であるため、PSPACE ⊆ EXPTIMEであることを確認する1つの方法です。^[3]

決定問題が EXPTIME 完全であるとは、それが EXPTIME に属し、EXPTIME 内のすべての問題に多項式時間の多対一縮約が存在する場合です。言い換えると、一方のインスタンスをもう一方のインスタンスに変換して同じ答えを出す多項式時間アルゴリズムが存在します。EXPTIME 完全な問題は、EXPTIME で最も難しい問題であると考えられます。NP が P に等しいかどうかは不明ですが、EXPTIME 完全な問題が P に属していないことはわかっています。時間階層定理により、これらの問題は多項式時間で解決できないことが証明されています。

計算可能性理論では、基本的な決定不能問題の 1 つに停止問題、つまり決定性チューリングマシン(DTM) が停止するかどうかを決定する問題があります。最も基本的な EXPTIME 完全問題の 1 つは、この問題のより単純なバージョンで、与えられた入力に対して DTM が最大kステップで停止するかどうかを問うものです。これは EXPTIME に属する問題です。なぜなら、単純なシミュレーションには O( k ) 時間かかり、入力k はO(log k ) ビットでエンコードされるため、指数関数的な回数のシミュレーションが発生するからです。これは EXPTIME 完全である理由は、大まかに言えば、これを使用して EXPTIME 問題を解くマシンが指数関数的な回数のステップで受け入れるかどうかを判断でき、それ以上の回数は使用しないからです。^[4]ステップ数を単項で記述した同じ問題はP 完全です。

EXPTIME完全問題の他の例としては、一般化チェス[5]、チェッカー[6]、囲碁[7]（日本のコルールを使用）の位置を評価する問題が挙げられる。これら の^ゲーム は^、盤の大き^さに比例する手数でゲームが続くことがあるため、EXPTIME完全である可能性がある。囲碁の例では、日本のコルールはEXPTIME完全性を意味することが知られているが、このゲームのアメリカや中国のルールがEXPTIME完全であるかどうかはわかっていない（PSPACEからEXPSPACEの範囲である可能性がある）。

対照的に、盤面の大きさの多項式の数の移動で終了する一般化されたゲームは、多くの場合PSPACE 完全です。繰り返しが自動で行われる指数関数的に長いゲームでも同じことが言えます。

EXPTIME完全問題のもう一つの重要なセットは、簡潔回路に関連しています。簡潔回路は、いくつかのグラフを指数的に小さいスペースで記述するために使用される単純な機械です。2つの頂点番号を入力として受け取り、それらの間に辺があるかどうかを出力します。グラフが隣接行列などの自然な表現で表現される多くの自然なP完全グラフ問題では、入力が指数的に小さいため、簡潔回路表現で同じ問題を解くことはEXPTIME完全です。しかし、簡潔回路はグラフのサブクラスしか記述できないため、これには非自明な証明が必要です。^[8]