EXPTIME
维基百科,自由的 encyclopedia
在计算复杂性理论里面,EXPTIME(有时称作EXP)这个复杂度类是一些决定型问题的集合,这些问题可以使用图灵机在O(2p(n))的时间内解决,这里的p(n)代表的是n的某个多项式。
此条目包含过多行话或专业术语,可能需要简化或提出进一步解释。 (2015年4月21日) |
用DTIME来定义,则是
我们已经知道
另外,根据时间谱系理论(time hierarchy theorem)以及空间谱系理论(space hierarchy theorem),
- P EXPTIME 且 NP NEXPTIME 且 PSPACE EXPSPACE
所以至少第一条包含关系中,前三个包含关系中的一个,以及后三个包含关系中的一个,必然是完整包含(没有相等可能),但是我们还不知道那一个是。多数人相信这一些复杂度类全部都不相等。另外我们已知如果P = NP,则EXPTIME = NEXPTIME,这里的NEXPTIME是在指数时间内可以使用非确定型图灵机解决的问题。[1]更精确的说,EXPTIME ≠ NEXPTIME当且仅当存在一个稀疏语言,在NP里面且不在P内。[2]
EXPTIME也可以用空间的方式来定义,等同于APSPACE这个复杂度类。APSPACE的意思是包含了所有可以用交替式图灵机在多项式空间内解决的问题。这种定义方式也是一种看出PSPACE EXPTIME的方式,因为已知交替式图灵机至少跟确定型图灵机计算能力一样。[3]
EXPTIME是指数谱系(exponential hierarchy)内的其中一个复杂度类。2-EXPTIME这个复杂度类则使用类似EXPTIME的定义方式,但是使用双指数函数(Double exponential function)的时间限制。使用类似方式可以类推出更高的时间上限。