卡普论文：NP 完全性的启示1972 年，理查德·卡普（Richard Karp）的论文《组合问题中的可归约性》横空出世

中本聪大学

卡普论文：NP 完全性的启示
1972 年，理查德·卡普（Richard Karp）的论文《组合问题中的可归约性》横空出世，它不仅是计算机科学的里程碑，更是一次对计算本质的深刻探索。
哥德尔与递归函数
早在 20 世纪 30 年代，哥德尔（Kurt Gödel）就提出了递归函数（recursive function）的概念。递归函数是一种可以通过自身调用的函数，它在数学和计算机科学中都有着重要的应用。哥德尔证明了，存在一些递归函数，我们无法确定它们是否会在有限时间内停止。
图灵与可计算性
与此同时，图灵（Alan Turing）提出了图灵机（Turing machine）的模型。图灵机是一种抽象的计算设备，它可以模拟任何计算过程。图灵证明了，存在一些问题，图灵机无法在有限时间内给出答案，即存在不可计算问题（uncomputable problem）。
卡普与 NP 完全性
卡普的论文将哥德尔的递归函数和图灵的可计算性理论与实际问题联系起来。他证明了一系列重要的组合问题，如旅行商问题、集合覆盖问题等，都属于 NP 完全问题。NP 完全问题是指，如果存在一个多项式时间算法可以解决其中任何一个问题，那么所有 NP 问题都可以用多项式时间算法解决。
然而，至今为止，我们尚未找到任何一个 NP 完全问题的多项式时间算法，P 是否等于 NP 仍然是计算机科学中最大的未解之谜。
总结
卡普的论文揭示了计算的局限性。有些问题，我们虽然可以验证解的正确性，但却难以找到解本身。这不仅是计算机科学的挑战，也是对人类认知能力的挑战。卡普的工作不仅推动了计算复杂性理论的发展，也引发了人们对计算、知识和世界本质的深刻思考。