查看“︁2-EXPTIME”︁的源代码

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

用[[DTIME]]的方式說明，

:<math> \mbox{2-EXPTIME} = \bigcup_{k \in \mathbb{N} } \mbox{ DTIME } \left( 2^{ 2^{n^k} } \right) . </math>

我們已經知道

:[[P (複雜度)|P]] <math>\subseteq</math> [[NP (複雜度)|NP]] <math>\subseteq</math> [[PSPACE]] <math>\subseteq</math>[[EXPTIME]] <math>\subseteq</math> [[NEXPTIME]] <math>\subseteq</math> [[EXPSPACE]] <math>\subseteq</math> 2-EXPTIME <math>\subseteq</math> [[ELEMENTARY]].

2-EXPTIME也可以被重構成AEXPSPACE這個空間複雜度類(使用[[交替式圖靈機]]可以在指數空間內解決的問題)。因為交替式圖靈機至少有跟決定型圖靈機一樣的計算力，所以這也是一個看出EXPSPACE <math>\subseteq</math> 2-EXPTIME的方式。<ref>Christos Papadimitriou, Computational Complexity (1994), ISBN 9780201530827. Section 20.1, corollary 3, page 495.</ref>

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

==2-EXPTIME-完全問題==

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

一般化的部份資訊可觀察遊戲(partially observable problems)相較於全部資訊可觀察的遊戲，其困難度則從[[EXPTIME]]-完全問題變成了2-EXPTIME-完全問題。<ref>{{ cite journal | author = Jussi Rintanen | title = [http://www.informatik.uni-freiburg.de/~ki/papers/Rintanen03compl.pdf Complexity of Planning with Partial Observability] | journal = Proceedings of International Conference on Automated Planning and Scheduling | publisher = AAAI Press | pages = 345–354 | year = 2004 }}</ref>

==相關頁面==
* [[雙重指數]]

==參考資料==
<references/>

{{複雜度類}}



[[Category:複雜度類]]