2-EXPTIME
维基百科,自由的 encyclopedia
在计算复杂度理论内,2-EXPTIME这个复杂度类 (有时写作2-EXP)是在O(22p(n))时间内,可以使用决定型图灵机解决掉决定型问题的集合,这里 p(n) 是n的一个多项式
用DTIME的方式说明,
我们已经知道
2-EXPTIME也可以被重构成AEXPSPACE这个空间复杂度类(使用交替式图灵机可以在指数空间内解决的问题)。因为交替式图灵机至少有跟决定型图灵机一样的计算力,所以这也是一个看出EXPSPACE 2-EXPTIME的方式。[1]
2-EXPTIME这个复杂度类,是在一种可以不断提升时间上限的复杂度类层级里面的其中一类。像3-EXPTIME 这个类别,类似于2-EXPTIME的定义方式,可以用三倍指数时间限制 来定义。用同样的方法可以定义出更高的时间上限(4-EXP,5-EXP…之类)。