形式陈述

指数时间类通常定义为 $\mathrm{EXP}=\bigcup _{k\ge 1}\mathrm{DTIME}(2^{n^k})$；采用 $2^{\mathrm{poly}(n)}$ 的等价写法。确定性时间层级定理给出 $P⊊EXP$。任何多项式空间计算只有 $2^{\mathrm{poly}(n)}$ 个配置，若停机则可在指数时间内模拟，故 $PSPACE\subseteq EXP$；是否严格包含未知。EXP 不应与 $E=\mathrm{DTIME}(2^{O(n)})$ 混同。

直觉

EXP 允许随输入长度的多项式进入指数，能穷举指数规模的候选或配置空间，但仍远小于双指数及更高时间类。

例子与边界

对 $n$ 个布尔变量枚举全部 $2^n$ 个赋值属于单指数时间。一个 $2^{n^2}$ 时间算法仍在 EXP；$2^{2^n}$ 则不在该定义给出的上界中。EXP 完全问题的输入常以简洁方式描述指数大对象，例如广义棋盘游戏或 succinct 结构。由 $P\ne EXP$ 不能推出 $P\ne NP$，因为 NP 可能仍等于 P 而 EXP 更大。

推论与应用

EXP 是时间层级中的首个标准指数层，作为复杂博弈、简洁表示问题和模型检查上界的自然容器，也为比较 PSPACE、NEXP 等类别提供基准。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Chs. 1–8。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 0–10。