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-完全问题。

相关页面

• 双重指数