2-EXPTIME

维基百科,自由的百科全书
跳转至: 导航搜索

計算複雜度理論內,2-EXPTIME這個複雜度類 (有時寫作2-EXP)是在O(22p(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 \subseteqEXPTIME \subseteq NEXPTIME \subseteq EXPSPACE \subseteq 2-EXPTIME \subseteq ELEMENTARY.

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

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-完全問題。[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.