×


系統正在處理中....

窗口將在 5 秒后自動關閉.

  1.   首頁  
  2. |
  3.   產品專區  
  4. |
  5.   加值服務  
  6. |
  7.   客戶服務  
  8. |
  9.   企業專區  
  10. |
  11.   網路商城  
 
跨平台產品
Dr.eye PLUS
Dr.eye Quiz
 
家用産品
Dr.eye 365
Dr.eye 譯典通 X
Dr.eye 譯典通 X 升級版
 
行動産品
Dr.eye 雲端免費版
Dr.eye 雲端版 - 日語通
Dr.eye 雲端版 - 韓語通
Dr.eye Mobile for Android
Dr.eye Mobile for iPhone
 
硬體産品
Dr.eye 翻譯小子 X
Dr.eye 翻譯小子 3
 
過往產品
Dr.eye 譯典通 9.0 旗艦版
Dr.eye 譯典通 9.0 旗艦升級版
Dr.eye 譯典通 9.0 全民版
 
 
EXP  
添加到生字筆記
權威釋義


維基百科

在計算複雜性理論裡面,EXPTIME(有時稱作EXP)這個複雜度類是一些決定型問題的集合,這些問題可以使用圖靈機在O(2p(n))的時間內解決,這裡的p(n)代表的是n的某個多項式。

用DTIME來定義,則是

EXPTIME = k N  DTIME  ( 2 n k ) {\displaystyle {\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{n^{k}}\right)}

我們已經知道

P {\displaystyle \subseteq } NP {\displaystyle \subseteq } PSPACE {\displaystyle \subseteq } EXPTIME {\displaystyle \subseteq } NEXPTIME {\displaystyle \subseteq } EXPSPACE

另外,根據時間譜系理論(time hierarchy theorem)以及空間譜系理論(space hierarchy theorem),

P {\displaystyle \subsetneq } EXPTIME 且 NP {\displaystyle \subsetneq } NEXPTIME 且 PSPACE {\displaystyle \subsetneq } EXPSPACE

所以至少第一條包含關係中,前三個包含關係中的一個,以及後三個包含關係中的一個,必然是完整包含(沒有相等可能),但是我們還不知道那一個是。多數人相信這一些複雜度類全部都不相等。另外我們已知如果P = NP,則EXPTIME = NEXPTIME,這裡的NEXPTIME是在指數時間內可以使用非確定型圖靈機解決的問題。更精確的說,EXPTIMENEXPTIME若且唯若存在一個稀疏語言,在NP裡面且不在P內。

EXPTIME也可以用空間的方式來定義,等同於APSPACE這個複雜度類。APSPACE的意思是包含了所有可以用交替式圖靈機在多項式空間內解決的問題。這種定義方式也是一種看出PSPACE {\displaystyle \subseteq } EXPTIME的方式,因為已知交替式圖靈機至少跟確定型圖靈機計算能力一樣。

EXPTIME是指數譜系(exponential hierarchy)內的其中一個複雜度類。2-EXPTIME這個複雜度類則使用類似EXPTIME的定義方式,但是使用雙指數函數(Double exponential function)的時間限制 2 2 n {\displaystyle 2^{2^{n}}} 。使用類似方式可以類推出更高的時間上限。



聯絡我們

客服專線 : (02)77378801
客服信箱 : service@dreye.com
服務時間 : 週一至週五 09:00~11:40 12:40~17:00 國定假日休息
購買鏈接
PC
Mobile
加入粉絲團


2017 Inventec Besta Co.,Ltd. All rights reserved
無敵科技股份有限公司版權所有
   隱私權聲明