复杂性类 EXP

EXP 允许确定性运行时间为 $2^{n^{O(1)}}$，因而能穷举指数规模的候选或配置空间，但仍远小于双指数及更高时间类。这里的“指数”指指数的指数项为多项式，而不是某个固定 $2^n$；因此 $2^{n^3}$ 和 $3^{\sqrt{n}}$ 都可落入相应上界。它仍是可判定问题类，只是预算随输入长度指数增长；时间层级定理保证 EXP 严格包含 P，这是少数已知的无条件复杂度分离。

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

暴力枚举 $n$ 位候选并对每个候选做多项式检查通常花费 $2^n\mathrm{poly}(n)$，属于 EXP。一个运行 $2^{2^n}$ 步的算法则通常超出 EXP，进入双指数时间。

“实际不可运行”不是类定义：对很小输入，指数算法可能可用；某些多项式算法也可能常数巨大。EXP 完全性依赖归约类型，不能仅因某问题有指数时间算法就称其 EXP 完全。

EXP 是时间层级中的首个标准指数层，作为复杂博弈与简洁表示问题的自然容器，也为比较 PSPACE、NEXP 等类别提供基准。某个模型检查问题公理库模型检查问题Model checking problem · Model checking给定系统模型与形式规格，判定所有指定初始行为是否满足公式，并交付证明结果或诊断见证。落入 EXP，通常来自输入对指数大状态空间的简洁编码以及特定逻辑的求值算法；状态系统、规格语义和算法复杂度是三项独立参数，不能把“模型检查”整体归入一个复杂性类。

它是 确定性时间类公理库确定性时间复杂性类Deterministic time class · DTIME由确定性图灵机在给定时间界内判定的语言集合。 的一个并集定义，并通过 时间层级定理公理库时间层级定理Time hierarchy theorem在可构造时间界下，给予更多渐近时间会严格扩大可判定语言类。 与 P公理库复杂度类 PP · Polynomial time能由确定性算法在输入长度的多项式时间内判定的语言集合。 严格分离。基本包含链把 PSPACE 放入 EXP；广义棋类、简洁编码博弈和某些逻辑模型检查问题常出现 EXP 完全性。