CookLevin Theorem
释义 Definition
库克列文定理：理论计算机科学中的一个核心定理，说明布尔可满足性问题（SAT）是 NP-完全（NP-complete）的。更具体地说：
- SAT 属于 NP；并且
- 任意 NP 问题都可以在多项式时间内归约（reduce）到 SAT。
因此，SAT 成为第一个被证明为 NP-完全的问题，奠定了 NP-完全性理论与复杂性理论的基础。（该术语也常写作 Cook’s theorem 或 CookLevin theorem。）
发音 Pronunciation (IPA)
/kk livn θirm/
例句 Examples
SAT was the first problem proven NP-complete by the CookLevin theorem.
SAT 是第一个由库克列文定理证明为 NP-完全的问题。
The CookLevin theorem implies that if we can solve SAT in polynomial time, then every problem in NP can also be solved in polynomial time.
库克列文定理意味着：如果我们能在多项式时间内解决 SAT，那么 NP 中的所有问题也都能在多项式时间内解决。
词源 Etymology
该定理以两位学者命名：Stephen Cook（斯蒂芬库克）与Leonid Levin（列奥尼德列文）。Cook 在 1971 年提出并证明了 SAT 的 NP-完全性（常称 Cook’s theorem），Levin 在相近时期以独立方式得到相似结论；后来的文献通常合称为 CookLevin theorem。其中 theorem 源自希腊语 theōrēma，意为“可被证明的命题/定理”。
相关词 Related Words
文献与著作 Literary / Notable Works
- Introduction to the Theory of Computation（Michael Sipser）在 NP-完全性章节中讲解 CookLevin 定理与 SAT 的地位。
- Computers and Intractability: A Guide to the Theory of NP-Completeness（Garey & Johnson）NP-完全性经典著作，讨论 SAT 与归约体系。
- Computational Complexity（Christos H. Papadimitriou）系统呈现复杂性理论背景与 CookLevin 定理的意义。
- Cook, S. A. (1971). “The Complexity of Theorem-Proving Procedures.”最早提出并证明 SAT 为 NP-完全的开创性论文之一。
- Levin, L. A.（1970s 相关工作）独立发展 NP-完全性思想并与 Cook 的结论并列引用。
Select Language