时间阶层定理

阐述

时间阶层定理联系了不同时间复杂度类。

时间可构造性

称一个函数 $f:N\to N$ 且 $f(n)\ge O(n\log n)$ 是时间可构造的，如果能以 $O(f(n))$ 时间将纸带上的 $1^n$ 转换为 $f(n)$ 的二进制表示。

定理

对于任何时间可构造函数 $f$ 来说，存在一个语言 $A$ 可以在 $O(f(n))$ 时间内判别，但不能在 $o(f(n)/\log f(n))$ 时间内判别。

推论：

• 如果 $f_1(n)=o(f_2(n)/\log f_2(n))$ 且 $f_2$ 可构造，那么 $\operatorname{TIME}\left(f_{1}(n)\right) \subsetneq \operatorname{TIME}\left(f_{2}(n)\right)$
• 对于任何实数 $0\le\varepsilon_1<\varepsilon_2$，$\operatorname{TIME}\left(n^{\epsilon_{1}}\right) \subsetneq \operatorname{TIME}\left(n^{\epsilon_{2}}\right)$
• $\mathrm{P} \subsetneq \mathrm{EXPTIME}$

实例

性质

相关内容

参考文献