理查德·卡普（Richard Karp）在 1972 年发表的论文《组合问题中的可归约性》（Reducibility Among Combinatorial Problems）是计算机科学领域的一篇重要论文，它奠定了计算复杂性理论的基础，特别是关于 NP 完全性概念的理解。 #核心思想： 这篇论文的核心思想是证明了一系列重要的组合问题都具有相同的计算难度，即它们都属于 NP 完全问题。这意味着，如果其中任何一个问题存在高效的解法（可以在多项式时间内解决），那么所有 NP 问题都将存在高效的解法，也就是 P = NP。然而，P 是否等于 NP 是计算机科学中最著名的未解难题之一。 #主要贡献： 定义了多项式时间归约的概念： 卡普引入了多项式时间归约的概念，这是一种将一个问题转换为另一个问题的方法，并且转换过程可以在多项式时间内完成。如果问题 A 可以多项式时间归约到问题 B，那么问题 A 的难度不会超过问题 B。 证明了 21 个经典问题是 NP 完全的： 卡普证明了包括集合覆盖、顶点覆盖、哈密顿回路、旅行商问题等 21 个经典组合问题都是 NP 完全的。这些问题涵盖了图论、集合论、逻辑等多个领域，它们的 NP 完全性表明了这类问题在计算上的困难性。 奠定了 NP 完全性理论的基础： 卡普的论文为 NP 完全性理论的发展奠定了基础。他的研究成果不仅加深了人们对计算复杂性的理解，也为后续的研究提供了重要的工具和方法。 #重要性： 卡普的论文“组合问题中的可归约性”是计算复杂性理论的里程碑式作品。它： 确立了 NP 完全性概念的重要性： NP 完全问题是计算机科学中最具挑战性的问题之一，理解 NP 完全性对于研究算法、人工智能等领域都具有重要意义。 推动了计算复杂性理论的发展： 卡普的工作激发了大量的研究，人们开始关注各种问题的计算复杂性，并尝试寻找高效的算法。 影响了实际应用： 对 NP 完全问题的研究成果在很多实际应用中都有重要意义，例如密码学、优化问题等。 总而言之，理查德·卡普的论文“组合问题中的可归约性”是计算机科学领域的一篇经典之作，它为计算复杂性理论的发展做出了卓越贡献，至今仍具有重要影响力。