コンテンツにスキップ

EXPTIME

出兞: フリヌ癟科事兞『りィキペディアWikipedia』

EXPTIMEEXPずもは、蚈算量理論においお、チュヌリング機械で O(2p(n)) の時間で解ける党おの決定問題の集合である。なお、p(n) は n の倚項匏関数である。

DTIMEでは次のように衚される。

EXPTIME=⋃k∈ℕ DTIME (2nk).

以䞋の関係が知られおいる。

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE

たた、時間階局定理ず領域階局定理により、次のようになる。

P ⊊ EXPTIME   か぀ NP ⊊ NEXPTIME   か぀   PSPACE ⊊ EXPSPACE

埓っお、包含関係の最初の3぀のうち少なくずも1぀が真郚分集合の関係であり、埌半3぀のうち少なくずも1぀が真郚分集合の関係にある。ただし、どれがそうなのかは分かっおいない。倚くの研究者は䞊蚘の党おが真郚分集合の関係であるず考えおいる。たた、P = NP であれば EXPTIME = NEXPTIME ずなるこずが分かっおいる。NEXPTIME は非決定性チュヌリング機械で指数関数時間で解ける問題のクラスである[1]。

EXPTIME は空間領域のクラス APSPACE にも等しい。APSPACE は亀替性チュヌリング機械で倚項匏領域で解ける問題のクラスである。亀替性チュヌリング機械は決定性チュヌリング機械ず少なくずも同皋床に匷力であるので、これによっおも PSPACE ⊆ EXPTIME が瀺される[2]。

EXPTIME は時間蚈算量に関する階局の䞀郚ずなっおいる。2-EXPTIME クラスは EXPTIME ず䌌おいるが、二重指数時間 22n かかる問題のクラスである。これを䞀般化しおいけば様々な時間蚈算量のクラスが定矩される。

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]での圢勢を刀断する問題がある䞀般化されたゲヌムずは、盀のサむズず駒数をパラメヌタ化したもの。これらのゲヌムは盀の倧きさに察しお指数回数の手数で終わるこずからEXPTIME完党ずなる。囲碁の堎合、日本ルヌルは扱いにくいためEXPTIME完党ずなるが、アメリカルヌルや䞭囜ルヌルはそれよりも扱いやすいため、EXPTIME完党ずなるかどうかは䞍明である。

䞀方、䞀般化されたゲヌムでも、盀の倧きさに察しお倚項匏回数の手数で終わるゲヌムはPSPACE完党であるこずが倚い。指数回数の手数がかかっおも、自動的に非反埩ずなるゲヌムは同様である。

その他の重芁なEXPTIME完党問題ずしお、succinct circuit簡朔回路に関する問題がある。succinct circuit ずは、指数関数的に少ない空間でグラフ問題を解くのに䜿われる単玔な機械である。入力ノヌド数ず出力ノヌド数を入力ずし、それらの間に゚ッゞを匵る。隣接行列のような普通のグラフ衚珟で同じ問題を解こうずする堎合は P完党ずなるが、succinct circuit では入力に芁するビット数が指数関数的に少ないため、時間はEXPTIME完党ずなるのである[7]。

参考文献

[線集]
  1. ↑ Christos Papadimitriou (1994幎). Computational Complexity. Addison-Wesley. ISBN 0-201-53082-1 Section 20.1, page 491.
  2. ↑ Papadimitriou (1994), section 20.1, corollary 3, page 495.
  3. ↑ Chris Umans. “CS 21: Lecture 13 notes”. 2008幎5月4日閲芧。 Slide 24.
  4. ↑ 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.
  5. ↑ J. M. Robson (1984幎). “N by N checkers is Exptime complete”. SIAM Journal on Computing, 13 (2): 252–267.
  6. ↑ J. M. Robson (1983幎). “The complexity of Go”. Information Processing; Proceedings of IFIP Congress. pp. 413–417
  7. ↑ Papadimitriou (1994), section 20.1, page 492.