2-EXPTIME

在計算複雜度理論內，2-EXPTIME這個複雜度類 (有時寫作2-EXP)是在O(2^2p(n))時間內，可以使用決定型圖靈機解決掉決定型問題的集合，這裏 p(n) 是n的一個多項式

用DTIME的方式說明，

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

我們已經知道

P $\subseteq$ NP $\subseteq$ PSPACE $\subseteq$EXPTIME $\subseteq$ NEXPTIME $\subseteq$ EXPSPACE $\subseteq$ 2-EXPTIME $\subseteq$ ELEMENTARY.

2-EXPTIME也可以被重構成AEXPSPACE這個空間複雜度類(使用交替式圖靈機可以在指數空間內解決的問題)。因為交替式圖靈機至少有跟決定型圖靈機一樣的計算力，所以這也是一個看出EXPSPACE $\subseteq$ 2-EXPTIME的方式。

2-EXPTIME這個複雜度類，是在一種可以不斷提昇時間上限的複雜度類層級裏面的其中一類。像3-EXPTIME 這個類別，類似於2-EXPTIME的定義方式，可以用三倍指數時間限制 $2^{2^{2^{n^{k}}}}$來定義。用同樣的方法可以定義出更高的時間上限(4-EXP，5-EXP…之類)。

2-EXPTIME-完全問題

許多一般化之後全部資訊可觀察的遊戲(fully observable games)是EXPTIME-完全問題。

一般化的部份資訊可觀察遊戲(partially observable problems)相較於全部資訊可觀察的遊戲，其困難度則從EXPTIME-完全問題變成了2-EXPTIME-完全問題。

相關頁面

• 雙重指數