EXPTIMEのソースを表示

'''EXPTIME'''（'''EXP'''とも）は、[[計算量理論]]において、[[チューリング機械]]で [[ランダウの記号|O]](2<sup>''p''(''n'')</sup>) の時間で解ける全ての[[決定問題]]の[[集合]]である。なお、''p''(''n'') は ''n'' の多項式関数である。

[[DTIME]]では次のように表される。

:<math> \mbox{EXPTIME} = \bigcup_{k \in \mathbb{N} } \mbox{ DTIME } \left( 2^{ n^k } \right) . </math>

以下の関係が知られている。

:[[P (計算量理論)|'''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''' &nbsp; かつ '''NP''' <math>\subsetneq</math> '''NEXPTIME''' &nbsp; かつ &nbsp; '''PSPACE''' <math>\subsetneq</math> '''EXPSPACE'''

従って、包含関係の最初の3つのうち少なくとも1つが真部分集合の関係であり、後半3つのうち少なくとも1つが真部分集合の関係にある。ただし、どれがそうなのかは分かっていない。多くの研究者は上記の全てが真部分集合の関係であると考えている。また、'''P'''&nbsp;=&nbsp;'''NP''' であれば '''EXPTIME'''&nbsp;=&nbsp;'''[[NEXPTIME]]''' となることが分かっている。'''NEXPTIME''' は[[非決定性チューリング機械]]で[[指数関数時間]]で解ける問題のクラスである<ref>{{cite book | author = Christos Papadimitriou | title = Computational Complexity | publisher = Addison-Wesley | date = 1994年 | id = ISBN 0-201-53082-1}} Section 20.1, page 491.</ref>。

'''EXPTIME''' は空間（領域）のクラス '''APSPACE''' にも等しい。'''APSPACE''' は[[交替性チューリング機械]]で多項式領域で解ける問題のクラスである。交替性チューリング機械は決定性チューリング機械と少なくとも同程度に強力であるので、これによっても '''PSPACE''' <math>\subseteq</math> '''EXPTIME''' が示される<ref>Papadimitriou (1994), section 20.1, corollary 3, page 495.</ref>。

'''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 となる<ref>{{cite web | author = Chris Umans | url = http://www.cs.caltech.edu/~umans/cs21/lec13.pdf | title = CS 21: Lecture 13 notes|accessdate=2008-05-04}} Slide 24.</ref>。また、なぜ '''EXPTIME'''完全であると言えるかだが、大まかに言って、これを使ってある機械が'''EXPTIME'''問題を指数ステップで受理するかどうかを判定できるためであり、'''EXPTIME'''以上の時間は要しない。

他の'''EXPTIME'''完全問題としては、一般化された[[チェス]]<ref name="Fraenkel1981">{{cite journal | author = Aviezri Fraenkel and D. Lichtenstein | title = Computing a perfect strategy for n×n chess requires time exponential in n | journal = J. Comb. Th. A | issue = 31 | date = 1981年 | pages = 199–214}}</ref>、[[チェッカー]]<ref name="robson1984">{{cite journal | author = J. M. Robson | title = N by N checkers is Exptime complete | journal = SIAM Journal on Computing, | volume = 13 | issue = 2 | pages = 252–267 | date = 1984年}}</ref>、[[囲碁]]（日本ルール）<ref>{{Cite book | author = J. M. Robson | chapter = The complexity of Go | title = Information Processing; Proceedings of IFIP Congress | date = 1983年 | pages = 413–417}}</ref>での形勢を判断する問題がある（一般化されたゲームとは、盤のサイズと駒数をパラメータ化したもの）。これらのゲームは盤の大きさに対して指数回数の手数で終わることから'''EXPTIME'''完全となる。囲碁の場合、日本ルールは扱いにくいため'''EXPTIME'''完全となるが、アメリカルールや中国ルールはそれよりも扱いやすいため、'''EXPTIME'''完全となるかどうかは不明である。

一方、一般化されたゲームでも、盤の大きさに対して多項式回数の手数で終わるゲームは'''[[PSPACE]]'''完全であることが多い。指数回数の手数がかかっても、自動的に非反復となるゲームは同様である。

その他の重要な'''EXPTIME'''完全問題として、succinct circuit（簡潔回路）に関する問題がある。succinct circuit とは、指数関数的に少ない空間で[[グラフ理論|グラフ問題]]を解くのに使われる単純な機械である。入力ノード数と出力ノード数を入力とし、それらの間にエッジを張る。[[隣接行列]]のような普通のグラフ表現で同じ問題を解こうとする場合は [[P (計算量理論)|'''P'''完全]]となるが、succinct circuit では入力に要するビット数が指数関数的に少ないため、時間は'''EXPTIME'''完全となるのである<ref>Papadimitriou (1994), section 20.1, page 492.</ref>。

== 参考文献 ==
<references/>

{{複雑性クラス}}

[[Category:計算複雑性理論]]
[[Category:数学に関する記事]]