时间层级定理

通用机模拟一台运行 $T$ 步的固定多带机器，可用 $O(T\log T)$ 时间；这才是本版本对数间隙的来源。时间可构造性提供可执行时钟，足够大的时间间隙则吸收模拟常数。对角化让新机器在自己的编码输入上反转被模拟机器的答案，迫使每个较快候选至少错一次。

例如分离 $\mathrm{DTIME}(n)$ 与 $\mathrm{DTIME}(n^2)$：输入 $x$ 解码为机器 $M$（用可任意补长而不改变所编码机器的约定），新机器花 $O(n^2)$ 预算运行通用模拟器；若 $M(x)$ 在预算内停机，就反转其输出，否则输出 $0$。假设新语言由某台 $O(n)$ 时间机器 $M$ 判定，选足够长的该机器编码，$O(n\log n)$ 模拟开销就落在预算内，得到同一输入上答案相反的矛盾。补长步骤保证渐近界和依赖于 $M$ 的常数确实能被吸收；这不是对某个自然问题的下界证明。

对固定整数 $k\ge 1$，取 $t_1(n)=n^k$、$t_2(n)=n^{k+1}$ 可得严格包含，因此 $P$ 内存在无限时间层级；要分离整个多项式并集，可取 $t_1(n)=2^{\lceil \sqrt{n}\rceil }$、$t_2(n)=2^n$（有限小输入另行调整）。每个固定 $n^k$ 最终都不超过 $t_1$，而 $t_1\log t_1=o(t_2)$，故 $P\subseteq \mathrm{DTIME}(t_1)⊊\mathrm{DTIME}(t_2)\subseteq EXP$。这给出一份同时避开全部多项式预算的语言，而不是仅对每个 $k$ 分别找一个更慢语言。但定理不能直接推出 $P\ne NP$：后者比较确定性与非确定性，而非两个充分分离的确定性时间界。

具体机器模型会影响细粒度对数因子，但不会改变 P 与 EXP 这类多项式稳健结论。

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

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