Cook–Levin Theorem

释义 Definition

库克–列文定理：理论计算机科学中的一个核心定理，说明布尔可满足性问题（SAT）是 NP-完全（NP-complete）的。更具体地说：

• SAT 属于 NP；并且
• 任意 NP 问题都可以在多项式时间内归约（reduce）到 SAT。
  因此，SAT 成为第一个被证明为 NP-完全的问题，奠定了 NP-完全性理论与复杂性理论的基础。（该术语也常写作 Cook’s theorem 或 Cook–Levin theorem。）

发音 Pronunciation (IPA)

/kʊk ˈliːvɪn ˈθiərəm/

例句 Examples

SAT was the first problem proven NP-complete by the Cook–Levin theorem.
SAT 是第一个由库克–列文定理证明为 NP-完全的问题。

The Cook–Levin 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 在相近时期以独立方式得到相似结论；后来的文献通常合称为 Cook–Levin theorem。其中 theorem 源自希腊语 theōrēma，意为“可被证明的命题/定理”。

相关词 Related Words

• Np
• Np-Complete
• Sat
• Reduction
• Polynomial-Time
• Complexity-Theory
• P-Vs-Np
• Boolean-Satisfiability

文献与著作 Literary / Notable Works

• Introduction to the Theory of Computation（Michael Sipser）——在 NP-完全性章节中讲解 Cook–Levin 定理与 SAT 的地位。
• Computers and Intractability: A Guide to the Theory of NP-Completeness（Garey & Johnson）——NP-完全性经典著作，讨论 SAT 与归约体系。
• Computational Complexity（Christos H. Papadimitriou）——系统呈现复杂性理论背景与 Cook–Levin 定理的意义。
• Cook, S. A. (1971). “The Complexity of Theorem-Proving Procedures.”——最早提出并证明 SAT 为 NP-完全的开创性论文之一。
• Levin, L. A.（1970s 相关工作）——独立发展 NP-完全性思想并与 Cook 的结论并列引用。