论文主要意义
•
1972 年，卡普发表了他的那篇著名的论文：“组合问题中的可归
约性” (Reducibility among Combinatorial Problems ，见由 R ． E ．
Miller 和 J ． W ． Thatcher 所编纂，由 Plenum 出版社出版的
Complexity Of Computer Computa6ons 一书 ) 。卡普的论文发展和
加强了由库克提出的“ NP 完全性”理论，尤其是，库克仅证明了命
题演算的可满足问题是 NP 完全的，而卡普则证明了从组合优化
中引出的大多数经典问题，包括背包问题、覆盖问题、匹配问题、
分区问题、路径问题、调度问题等，都是 NP 完全问题。只要证
明其中任一个问题是属于 P 类的，就可解决计算复杂性理论中最
大的一个难题，即 P=?NP 。这就是卡普论文的主要贡献和主要意
义。
评论6