形式陈述

在标准多带确定性图灵机模型中，设 $t_1,t_2$$t_1,t_2$ 为适当的时间可构造函数，并满足

$$ t_1(n)\log t_1(n)=o(t_2(n)). $$$$t_1(n)\log t_1(n)=o(t_2(n)).$$

则确定性时间层级定理给出

$$ \operatorname{DTIME}(t_1(n)) \subsetneq \operatorname{DTIME}(t_2(n)). $$$$\mathrm{DTIME}(t_1(n))⊊\mathrm{DTIME}(t_2(n)).$$

具体的对数间隙取决于通用模拟所采用的机器模型；核心证明用带时钟的对角化构造一个在 $O(t_2)$$O(t_2)$ 时间内运行、却与每台 $O(t_1)$$O(t_1)$ 时间机器在其编码输入上不同的语言。

直觉

给算法更多时间确实能解决严格更多问题，但要留出通用模拟和自我编码的管理开销。对角化让新语言专门在第 $i$$i$ 个输入上反驳第 $i$$i$ 台较快机器。

例子与边界

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

推论与应用

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

参考资料

• Juris Hartmanis and Richard E. Stearns, “On the Computational Complexity of Algorithms,” Transactions of the American Mathematical Society 117, 1965, pp. 285–306，Full paper, diagonal hierarchy results。
• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Ch. 3。