EXPTIME
EXPTIME（EXPとも）は、計算量理論において、チューリング機械で O(2p(n)) の時間で解ける全ての決定問題の集合である。なお、p(n) は n の多項式関数である。
DTIMEでは次のように表される。
- [math] \mbox{EXPTIME} = \bigcup_{k \in \mathbb{N} } \mbox{ DTIME } \left( 2^{ n^k } \right) . [/math]
以下の関係が知られている。
- P [math]\subseteq[/math] NP [math]\subseteq[/math] PSPACE [math]\subseteq[/math] EXPTIME [math]\subseteq[/math] NEXPTIME [math]\subseteq[/math] EXPSPACE
- P [math]\subsetneq[/math] EXPTIME かつ NP [math]\subsetneq[/math] NEXPTIME かつ PSPACE [math]\subsetneq[/math] EXPSPACE
従って、包含関係の最初の3つのうち少なくとも1つが真部分集合の関係であり、後半3つのうち少なくとも1つが真部分集合の関係にある。ただし、どれがそうなのかは分かっていない。多くの研究者は上記の全てが真部分集合の関係であると考えている。また、P = NP であれば EXPTIME = NEXPTIME となることが分かっている。NEXPTIME は非決定性チューリング機械で指数関数時間で解ける問題のクラスである[1]。
EXPTIME は空間（領域）のクラス APSPACE にも等しい。APSPACE は交替性チューリング機械で多項式領域で解ける問題のクラスである。交替性チューリング機械は決定性チューリング機械と少なくとも同程度に強力であるので、これによっても PSPACE [math]\subseteq[/math] EXPTIME が示される[2]。
EXPTIME は時間計算量に関する階層の一部となっている。2-EXPTIME クラスは EXPTIME と似ているが、二重指数時間 [math]2^{2^n}[/math] かかる問題のクラスである。これを一般化していけば様々な時間計算量のクラスが定義される。
EXPTIME-完全
ある EXPTIME の決定問題が EXPTIME完全であるとき、EXPTIME のあらゆる問題をその問題に多項式時間多対一還元できる。言い換えれば、ある問題の具体例を別の問題の具体例に多項式時間で変換するアルゴリズムがあり、その解が変わらない。EXPTIME完全の問題は EXPTIME の問題の中で最も難しいと考えられる。NP と P が包含関係にあるかどうかは分からないが、EXPTIME完全な問題が P に属さないことは分かっている。これは、EXPTIME完全な問題が多項式時間で解けないことを示すことで証明された。
計算可能性理論において、基本的な判定不能問題は決定性チューリング機械(DTM)がある入力を受理するかどうかの決定問題である。最も基本的なEXPTIME完全問題はこれを単純化したもので、あるDTMがある入力を最大 k ステップ以内に受理するかどうかの判定問題である。この問題は自明なシミュレーションが O(k) 時間かかり、入力 k が O(log k) ビットで符号化されることから EXPTIME となる[3]。また、なぜ EXPTIME完全であると言えるかだが、大まかに言って、これを使ってある機械がEXPTIME問題を指数ステップで受理するかどうかを判定できるためであり、EXPTIME以上の時間は要しない。
他のEXPTIME完全問題としては、一般化されたチェス[4]、チェッカー[5]、囲碁（日本ルール）[6]での1つの位置の評価問題がある（一般化されたゲームとは、盤のサイズと駒数をパラメータ化したもの）。これらのゲームは盤の大きさに対して指数回数の手数で終わることからEXPTIME完全となる。囲碁の場合、日本ルールは扱いにくいためEXPTIME完全となるが、アメリカルールや中国ルールはそれよりも扱いやすいため、EXPTIME完全となるかどうかは不明である。
一方、一般化されたゲームでも、盤の大きさに対して多項式回数の手数で終わるゲームはPSPACE完全であることが多い。指数回数の手数がかかっても、自動的に非反復となるゲームは同様である。
その他の重要なEXPTIME完全問題として、succinct circuit（簡潔回路）に関する問題がある。succinct circuit とは、指数関数的に少ない空間でグラフ問題を解くのに使われる単純な機械である。入力ノード数と出力ノード数を入力とし、それらの間にエッジを張る。隣接行列のような普通のグラフ表現で同じ問題を解こうとする場合は P完全となるが、succinct circuit では入力に要するビット数が指数関数的に少ないため、時間はEXPTIME完全となるのである[7]。
参考文献
- ↑ Christos Papadimitriou (1994年). Computational Complexity. Addison-Wesley. ISBN 0-201-53082-1. Section 20.1, page 491.
- ↑ Papadimitriou (1994), section 20.1, corollary 3, page 495.
- ↑ Chris Umans. “CS 21: Lecture 13 notes”. . 2008閲覧. Slide 24.
- ↑ Aviezri Fraenkel and D. Lichtenstein (1981年). “Computing a perfect strategy for n×n chess requires time exponential in n”. J. Comb. Th. A (31): 199–214.
- ↑ J. M. Robson (1984年). “N by N checkers is Exptime complete”. SIAM Journal on Computing, 13 (2): 252–267.
- ↑ J. M. Robson (1983年). “The complexity of Go”, Information Processing; Proceedings of IFIP Congress, 413–417.
- ↑ Papadimitriou (1994), section 20.1, page 492.