EXPTIME EXPTIME
(重定向自EXP)
在计算复杂性理论里面,EXPTIME(有时称作EXP)这个复杂度类是一些决定型问题的集合,这些问题可以使用图灵机在O(2)的时间内解决,这里的p(n)代表的是n的某个多项式。
用DTIME来定义,则是
我们已经知道
另外,根据时间谱系理论(time hierarchy theorem)以及空间谱系理论(space hierarchy theorem),
所以至少第一条包含关系中,前三个包含关系中的一个,以及后三个包含关系中的一个,必然是完整包含(没有相等可能),但是我们还不知道那一个是。多数人相信这一些复杂度类全部都不相等。另外我们已知如果P = NP,则EXPTIME = NEXPTIME,这里的NEXPTIME是在指数时间内可以使用非确定型图灵机解决的问题。更精确的说,EXPTIME ≠ NEXPTIME若且唯若存在一个稀疏语言,在NP里面且不在P内。