复杂性类 EXP

EXP 允许指数中的量是输入长度的多项式，因此 $2^n$、$2^{n^2}$ 和 $2^{n^3}$ 都在预算内。它覆盖的范围比 $E=\mathrm{DTIME}(2^{O(n)})$ 更广：E 把指数限制为线性量级，EXP 则允许任意固定次数的多项式。这使 EXP 能容纳对指数规模候选或配置空间的完整搜索。

对 $n$ 个布尔变量枚举全部 $2^n$ 个赋值，再逐一做多项式时间检查，总时间为 $2^n\mathrm{poly}(n)$，属于 EXP。若输入用简短编码描述一个指数大的对象，显式展开它也可能消耗指数时间；广义棋盘游戏和简洁表示的结构常由此产生 EXP 完全问题。

时间 $2^{2^n}$ 超出了 EXP 的预算，但发现一个如此缓慢的算法，并不能说明问题本身不属于 EXP：同一问题可能有更快算法。类似地，一个指数时间上界只能证明成员资格；EXP 完全性还需要相应归约下的困难性证明。

$P\ne EXP$ 也不能推出 $P\ne NP$。时间层级定理分离了 P 与 EXP，而 NP 在它们之间的位置仍允许 $P=NP$。

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