2-EXPTIME

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

用DTIME的方式說明，

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

我們已經知道

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

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

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

2-EXPTIME-完全問題

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

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

相關頁面

• 雙重指數

參考資料

1. Christos Papadimitriou, Computational Complexity (1994), ISBN 9780201530827. Section 20.1, corollary 3, page 495.
2. Jussi Rintanen. Complexity of Planning with Partial Observability. Proceedings of International Conference on Automated Planning and Scheduling (AAAI Press). 2004: 345–354.