檢視 EXPTIME 的原始碼

佇咧算複雜性理論內底，'''EXPTIME'''（有時叫做'''EXP'''）這个複雜度類是一寡決定型問題的集合，遮的問題會使使用圖靈機佇咧 O ( 二 p ( _ n _ ) ) 的時間內解決，遮的 _ p _ ( _ n _ ) 代表的是講 _ n _ 的某一个多項式按呢。

用 DTIME 來定義，著著


: $ { \ mbox { EXPTIME } }=\ bigcup _ { k \ in \ mathbb { N } } { \ mbox { DTIME } } \ left ( 二 ^ { n ^ { k } } \ right ) $

咱已經知影


: P $ \ subseteq $ NP $ \ subseteq $ PSPACE $ \ subseteq $ EXPTIME $ \ subseteq $ NEXPTIME $ \ subseteq $ EXPSPACE

另外咧，根據時間譜系理論（time hierarchy theorem）猶閣有空間譜系的理論（space hierarchy theorem），


: P $ \ subsetneq $ EXPTIME 而且 NP $ \ subsetneq $ NEXPTIME 而且 PSPACE $ \ subsetneq $ EXPSPACE

所以至少第一條包含關係中，這个前三个包含關係中的一个，以及後三个包括關係中的一个，必然是完整包括（無相等可能）， 但是阮猶閣毋知影彼是。多數人相信講這一寡複雜度類完全攏無相等。另外咱已經知若是 P=NP，著 EXPTIME=NEXPTIME，遮的 NEXPTIME 是佇咧指數時間內會當使用非確定型圖靈機解決的問題。閣較精確的講，'''EXPTIME'''≠'''NEXPTIME'''若是唯一閣存在一个疏櫳語言，佇咧'''NP'''內底而且無佇咧'''P'''內。

EXPTIME 嘛會當用空間的方式來定義，等仝款 _ APSPACE _ 這个複雜度類。APSPACE 的意思是講包含著所有會使用交替式圖靈機佇咧多項式空間內解決的問題。這種定義方式嘛是一種看出 PSPACE $ \ subseteq $ EXPTIME 的方式，因為已經知影交替式圖靈機至少佮確定型圖靈機計算能力仝款。

EXPTIME 是指數譜系（exponential hierarchy）內底的其中一个複雜度類。二-EXPTIME 這个複雜度類似使用類似 EXPTIME 的定義方式，但是使用雙指數函數（Double exponential function）的時間限制 $ 二 ^ { 二 ^ { n } } $。使用類似方式會使類推出較懸的時間上限。

==EXPTIME-完全==

咱講一个問題是 EXPTIME-完全，若這个問題本身佇咧 EXPTIME 內，閣對任何 EXPTIME 內底的問題，均存在個多項式時間歸約的方法會當歸約成此問題。嘛會使講，存在一個多項式時間的演算法，將原來題目的輸入對應到另外一个問題的輸入，並且會當維持答案相仝。EXPTIME-完全問題嘛會使想欲做是 EXPTIME 內上難的問題。遮應該注意著，阮並毋知影 NP 敢有等同 P，但是咱有影知影講 EXPTIME-完全問題無包括佇 P 內；根據時間譜系理論，咱已經證實遮的問題無可能佇多項式時間內解決。

佇咧會當算性理論內，一个基本的非決定性問題是一个決定型圖靈機（DTM , deterministic turing machine）敢會使結束咧運作（一般講的 halting problem，停機的問題）。 有一个按呢問題的簡易版，詢問一个 DTM 敢會當佇 k 行內面結束運作，是 EXPTIME-完全中一个基本問題。這个問題是佇咧 EXPTIME 內底，因為單純使用圖靈機去模擬需要 O ( _ k _ ) 的時間，啊若輸入實際的資料披大細著 ( log _ k _ )。然後，咱知影這是 EXPTIME-完全問題。因為乎，用較粗略的講法，咱會使用這个問題，去決定一个機械敢有佇咧指數時間內底會當解決一个 EXPTIME 問題。若是阮共一模一樣的問題，彼工夫的數目使用一進位表示，這个問題變做講 P-完全。

其他 EXPTIME-完全問題的範例包括著推廣的西洋棋，國際跳棋，佮圍棋（使用日本的規則）。 遮的遊戲之所以可能是 EXPTIME-完全，因為遮的遊戲會當維持相對枋仔大細來講，可能移動的方式是指數成長。咧圍棋的例，日本的規則有夠困難到暗示其實 EXPTIME-完整性，但是咱並毋知影較簡單的美國抑是中國規則敢是閣敢是 EXPTIME-完全。

相對的乎，會當維持移動步數成長佮棋盤大細成外項式成長的推廣遊戲一般是 PSPACE-完全。對指數成長但是非常重複部份是自動處理遊戲，這嘛是仝款的。

另外一系列的 EXPTIME-完全問題佮簡潔電路（succinct circuit）相關。簡潔電路是用來指數速率減少的空間，來形容一寡種類的圖樣（gragh）， 的簡單機器。這機器接受兩个點的編號作為輸入值，輸出這兩點敢是相連。對濟濟使用自然的圖表示法（親像鄰接矩陣）時，佮圖有關係的 P-完全問題，換做使用簡潔電路表來解決仝款的問題，會變做是 EXPTIME-完全，因為輸入值佮圖大細相比是以指數速率減少；但是愛完整證出這个問題，需要一寡較複雜的證明，因為簡潔電路會當提來定義部份的圖。

==參考資料==

[[分類: 待校正]]