时间层级定理

时间层级定理用通用模拟加对角化说明，给算法更多时间确实能解决严格更多问题：它构造一门语言，在更大时间内模拟第 $i$ 台小时间机器，却在自己的编码输入上反转其结果，专门反驳相应较快机器，因此不可能由任何小时间机器判定。额外的对数因子来自为通用模拟、自我编码和计时留出的管理开销；时间可构造性确保预算可被机器有效维护。定理给出存在性分离，而非为自然问题自动生成下界。

取 $t_1(n)=n^k$、$t_2(n)=n^{k+1}$ 可得严格包含，因此 $P$ 内存在无限时间层级；取多项式族与指数族还可推出 $P\ne EXP$。但定理不能直接推出 $P\ne NP$：后者比较确定性与非确定性，而非两个充分分离的确定性时间界。

不能由 $P\ne EXP$ 推出 $P\ne NP$：NP 位于二者之间，严格差异可能发生在其他位置。具体机器模型会影响细粒度对数因子，但不会改变 P 与 EXP 这类多项式稳健结论。

时间层级定理证明复杂度类不会在所有可构造时间尺度上坍缩，并为“额外资源增加计算能力”提供严格结论。若时间界不可构造或间隙不足，不能无条件套用此版本。

它直接比较 确定性时间类公理库确定性时间复杂性类Deterministic time class · DTIME由确定性图灵机在给定时间界内判定的语言集合。，并无条件分离 P公理库复杂度类 PP · Polynomial time能由确定性算法在输入长度的多项式时间内判定的语言集合。 与 EXP公理库复杂性类 EXPEXPTIME · EXP可由确定性图灵机在单指数时间内判定的语言类。。与 空间层级定理公理库空间层级定理Space hierarchy theorem在适当空间可构造性条件下，更多渐近空间严格提升可判定语言能力。 对照，可看出通用模拟成本在两种资源中的不同；精细时间复杂度则尝试把这种层级思想推进到更自然的问题和更小差距。