确定性时间层次定理的内容是什么？为什么由它可以推出 P 是 EXPTIME 的真子集？
What does the deterministic time hierarchy theorem state, and why does it imply that P is a proper subset of EXPTIME?
定理断言：对任意时间可构造函数 t(n)，存在一个语言可在 O(t(n)) 时间内判定，却不能在 o(t(n)/log t(n)) 时间内判定；证明采用对角化方法，模拟所有运行时间较短的机器并对每个结果取反，构造出一个与之不同的语言。取 t(n)=2^n 可得一个属于 EXPTIME 的语言，而任何固定多项式 n^k 都满足 n^k = o(2^n/n)，故该语言不属于任何 DTIME(n^k)，也就不在 P 中，于是 P 是 EXPTIME 的真子集。
The theorem asserts that for every time-constructible function t(n), some language is decidable in O(t(n)) time but not in o(t(n)/log t(n)) time; the proof diagonalizes — it simulates each machine running within the smaller bound and flips its answer to define a new language. Choosing t(n) = 2^n yields a language in EXPTIME, while every fixed polynomial satisfies n^k = o(2^n/n), so that language lies outside every DTIME(n^k) and hence outside P. Therefore P is strictly contained in EXPTIME.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-03 · 2 条独立证据
来源 · Source
Michael Sipser,《Introduction to the Theory of Computation》第3版,Cengage Learning,2013,第8章 Time Complexity（确定性时间层次定理）
Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning, 2013, Chapter 8 (Time Complexity; Deterministic Time Hierarchy Theorem)
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL19859284W：Introduction to the th
#计算复杂性 #时间层次定理 #对角化法 #复杂度类
Toda 定理（1991）陈述了什么结论？它为什么说明 #P 计数问题的计算能力极强？
What does Toda's theorem (1991) state, and why does it show that #P counting problems are computationally very powerful?
该定理断言 PH ⊆ P^#P：整座多项式层级都可归约到带 #P 预言机的多项式时间。#P 函数统计非确定性图灵机的接受路径数目。证明以 Valiant–Vazirani 归约与 BP· 算子把量词交替压缩成一次计数询问。既然 PH 被普遍认为远超 NP，一次计数即可模拟全层级，足见计数之强。
Toda's theorem asserts PH ⊆ P^#P: the entire polynomial hierarchy collapses into polynomial time with a #P oracle, where #P functions count accepting paths of nondeterministic polynomial-time machines. The proof combines the Valiant–Vazirani unique-SAT reduction with the BP· operator to replace quantifier alternation by a single counting query. Since PH is widely believed to far exceed NP, one counting query simulating the whole hierarchy shows how powerful counting is.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-03
来源 · Source
S. Toda《PP is as hard as the polynomial-time hierarchy》（STOC 1991），SIAM Journal on Computing 20(4):865-877, 1991，DOI:10.1137/0220053
S. Toda, "PP is as hard as the polynomial-time hierarchy" (STOC 1991), SIAM Journal on Computing 20(4):865-877, 1991, DOI:10.1137/0220053
独立核验依据 · Independent verification: 核验依据 1 CROSSREF 标识 10.1137/0220053：PP is as Hard as the Polynom
#计算复杂性 #Toda定理 ##P #多项式层级
什么是 NP 完全问题？Cook–Levin 定理为何被视为计算复杂性理论的基石？
What is an NP-complete problem, and why is the Cook–Levin theorem regarded as a cornerstone of computational complexity theory?
NP 完全问题是 NP 中最难的一层：任何 NP 问题都可多项式时间归约到它。1971 年 Cook 证明布尔可满足性问题是 NP 完全的，Levin 也独立得到同一结论，首次确认此类问题存在。此后从 SAT 等已知完全问题构造多项式归约即可证出新问题的 NP 完全性；任一 NP 完全问题若有多项式算法即有 P=NP，大量实际难题的命运由此绑定。
An NP-complete problem is among the hardest in NP: every language in NP reduces to it in polynomial time. In 1971 Cook proved that Boolean satisfiability (SAT) is NP-complete, and Levin independently obtained the same result, establishing that such problems exist at all. Afterwards, proving a new problem NP-complete only requires a polynomial reduction from SAT or another known complete problem. Because a polynomial-time algorithm for any single NP-complete problem would imply P = NP, the theorem ties the fate of thousands of practical optimization problems together.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-11-03
来源 · Source
S. A. Cook，《定理证明过程的复杂性》，ACM 计算理论研讨会（STOC）论文集，1971，DOI: 10.1145/800157.805047
S. A. Cook, 'The Complexity of Theorem-Proving Procedures', Proc. 3rd ACM Symposium on Theory of Computing (STOC), 1971, DOI: 10.1145/800157.805047
独立核验依据 · Independent verification: 核验依据 1 CROSSREF 标识 10.1145/800157.805047：The complexity of theo
#NP完全性 #多项式归约 #布尔可满足性