https://wiki.taigi.ima.org.tw/w/index.php?action=history&feed=atom&title=%E4%BA%8C-EXPTIME
二-EXPTIME - 修訂紀錄
2026-05-02T22:26:04Z
本 wiki 上此頁面的修訂紀錄
MediaWiki 1.43.1
https://wiki.taigi.ima.org.tw/w/index.php?title=%E4%BA%8C-EXPTIME&diff=431755&oldid=prev
TaiwanTonguesApiRobot：從 JSON 檔案批量匯入
2025-08-22T16:43:37Z
<p>從 JSON 檔案批量匯入</p>
<p><b>新頁面</b></p><div>佇咧算複雜度理論內，'''二-EXPTIME'''這个複雜度類 ( 有時陣寫作'''二-EXP''') 是佇咧 O ( 二十二 p ( _ n _ ) ) 時間內，會使使用決定型圖靈機解決掉決定型問題的集合，遮 _ p _ ( _ n _ ) 是 _ n _ 的一項外用 DTIME 的方式說明，<br />
<br />
<br />
: $ { \ mbox { 二-EXPTIME } }=\ bigcup _ { k \ in \ mathbb { N } } { \ mbox { DTIME } } \ left ( 二 ^ { 二 ^ { n ^ { k } } } \ right ) . $<br />
<br />
咱已經知影<br />
<br />
<br />
: P $ \ subseteq $ NP $ \ subseteq $ PSPACE $ \ subseteq $ EXPTIME $ \ subseteq $ NEXPTIME $ \ subseteq $ EXPSPACE $ \ subseteq $ 二-EXPTIME $ \ subseteq $ ELEMENTARY .<br />
<br />
二-EXPTIME 嘛會當予重構成 AEXPSPACE 這个空間複雜度類 ( 使用交替式圖靈機會當佇指數空間內解決的問題 )。因為交替式圖靈機至少有佮決定型圖靈機仝款的計算力，所以這嘛是一个看出講 EXPSPACE $ \ subseteq $ 二-EXPTIME 的方式。<br />
<br />
二-EXPTIME 這个複雜度類，是佇一種會當不斷提昇時間上限的複雜度類層級內底的其中一類。像三-EXPTIME 這類別，類似二-EXPTIME 的定義方式，會當用三倍指數時間的限制 $ 二 ^ { 二 ^ { 二 ^ { n ^ { k } } } } $ 來定義。用仝款的方法會當定義出閣較懸的時間上限 ( 四-EXP，五-EXP…啥物貨 )。<br />
<br />
==二-EXPTIME-完全問題==<br />
<br />
真濟一般化了後全部資訊會當觀察的遊戲 ( fully observable games ) 是 EXPTIME-完全問題。<br />
<br />
一般化的部份資訊會當觀察遊戲 ( partially observable problems ) 和全部的資訊會當觀察的遊戲和，其困難度著對 EXPTIME-完全的問題變做二-EXPTIME-完全問題。<br />
<br />
==相關頁面==<br />
<br />
* 雙重指數<br />
<br />
==參考資料==<br />
<br />
[[分類: 待校正]]</div>
TaiwanTonguesApiRobot