EXPTIME

在计算复杂性理论里面，EXPTIME（有时称作EXP）这个复杂度类是一些决定型问题的集合，这些问题可以使用图灵机在O(2^p(n))的时间内解决，这里的p(n)代表的是n的某个多项式。

“EXP”重定向至此。关于函数，请见“指数函数”。关于游戏术语，请见“经验值”。

用DTIME来定义，则是

${\displaystyle {\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{n^{k}}\right)}$

我们已经知道

P ${\displaystyle \subseteq }$ NP ${\displaystyle \subseteq }$ PSPACE ${\displaystyle \subseteq }$ EXPTIME ${\displaystyle \subseteq }$ NEXPTIME ${\displaystyle \subseteq }$ EXPSPACE

另外，根据时间谱系理论（time hierarchy theorem）以及空间谱系理论（space hierarchy theorem），

P ${\displaystyle \subsetneq }$ EXPTIME 且 NP ${\displaystyle \subsetneq }$ NEXPTIME 且 PSPACE ${\displaystyle \subsetneq }$ EXPSPACE

所以至少第一条包含关系中，前三个包含关系中的一个，以及后三个包含关系中的一个，必然是完整包含（没有相等可能），但是我们还不知道那一个是。多数人相信这一些复杂度类全部都不相等。另外我们已知如果P = NP，则EXPTIME = NEXPTIME，这里的NEXPTIME是在指数时间内可以使用非确定型图灵机解决的问题。^[1]更精确的说，EXPTIME ≠ NEXPTIME若且唯若存在一个稀疏语言，在NP里面且不在P内。^[2]

EXPTIME也可以用空间的方式来定义，等同于APSPACE这个复杂度类。APSPACE的意思是包含了所有可以用交替式图灵机在多项式空间内解决的问题。这种定义方式也是一种看出PSPACE ${\displaystyle \subseteq }$ EXPTIME的方式，因为已知交替式图灵机至少跟确定型图灵机计算能力一样。^[3]

EXPTIME是指数谱系（exponential hierarchy）内的其中一个复杂度类。2-EXPTIME这个复杂度类则使用类似EXPTIME的定义方式，但是使用双指数函数（Double exponential function）的时间限制${\displaystyle 2^{2^{n}}}$。使用类似方式可以类推出更高的时间上限。

EXPTIME-完全

我们说一个问题是EXPTIME-完全，若这问题本身在EXPTIME内，且对任何EXPTIME内的问题，均存在一个多项式时间归约的方法可以归约成此问题。换句话说，存在一个多项式时间的演算法，将原来题目的输入对应到另一个问题的输入，并且能维持答案相同。EXPTIME-完全问题也可以想做是EXPTIME内最难的问题。这里应该注意到，我们并不知道NP是否等同P，但是我们确实知道EXPTIME-完全问题不包含在P内；根据时间谱系理论，我们已经证实这些问题不可能在多项式时间内解决。

在可计算性理论内，一个基本的非决定性问题是一个决定型图灵机（DTM, deterministic turing machine）是否能结束运作（一般说的halting problem，停机问题）。有一个此问题的简易版，询问一个DTM是否能在k步里面结束运作，是EXPTIME-完全中一个基本问题。这问题是在EXPTIME里面，因为单纯使用图灵机去模拟需要O(k)的时间，而输入实际的资料晾大小则是(log k)。^[4]然后，我们知道这是EXPTIME-完全问题。因为，用比较粗略的说法，我们可以使用这个问题，去决定一个机器是否在指数时间内可以解决一个EXPTIME问题。如果我们将一模一样的问题，步骤的数目使用一进位表示，这问题则变成P-完全。

其他EXPTIME-完全问题的范例包括了推广的西洋棋,^[5] 国际跳棋,^[6]以及围棋（使用日本的规则）。^[7]这些游戏之所以可能是EXPTIME-完全，因为这些游戏可以维持相对板子大小而言，可能移动方式是指数成长。在围棋的例子，日本的规则足够困难到暗示了其EXPTIME-完整性，但是我们并不知道比较简单的美国或者中国规则是否还是EXPTIME-完全。

相对的，可以维持移动步数成长跟棋盘大小成多项式成长的推广游戏一般是PSPACE-完全。对指数成长但是非重复部份是自动处理的游戏，这也是一样的。

另一系列的EXPTIME-完全问题与简洁电路（succinct circuit）相关。简洁电路是用来以指数速率减少的空间，来形容一些种类的图（gragh），的简单机器。这机器接受两个点的编号作为输入值，输出这两个点是否相连。对许多使用自然的图表示法（像是邻接矩阵）时，与图相关的P-完全问题，换成使用简洁电路表来解决相同的问题，会变成EXPTIME-完全，因为输入值跟图大小相比是以指数速率减少；但是要完整证出这个问题，需要一些比较复杂的证明，因为简洁电路只能用来定义部份的图。^[8]

参考资料

1. Christos Papadimitriou. Computational Complexity. Addison-Wesley. 1994. ISBN 0201530821. Section 20.1, page 491.
2. Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, volume 65, issue 2/3, pp.158–181. 1985. At ACM Digital Library Archive.is的存档，存档日期2012-07-12
3. Papadimitriou (1994), section 20.1, corollary 3, page 495.
4. Chris Umans. CS 21: Lecture 16 notes (PDF). [2011-04-09]. （原始内容 (PDF)存档于2011-06-08）. Slide 21.
5. Aviezri Fraenkel and D. Lichtenstein. Computing a perfect strategy for n×n chess requires time exponential in n. J. Comb. Th. A. 1981, (31): 199–214.
6. J. M. Robson. N by N checkers is Exptime complete. SIAM Journal on Computing,. 1984, 13 (2): 252–267. doi:10.1137/0213018.
7. J. M. Robson. The complexity of Go. Information Processing; Proceedings of IFIP Congress. 1983: 413–417.
8. Papadimitriou (1994), section 20.1, page 492.