3.P和NP

高效能计算的正确定义来自20世纪60年代的两篇论文，分别是杰克·埃德蒙兹的“路径、树木与花朵”（Paths, Trees and Flowers）和艾伦·科巴姆的“函数的内在计算难度”（The Intrinsic Computational Difficulty of Functions）。

埃德蒙兹论文最重要的贡献是给出了配对问题的首个有效算法，这在第3章讨论过了。论文有一节叫“题外话”，埃德蒙兹在里面讨论了指数和代数级别的区别，不过他不建议为算法的效率设定任何严格的标准：

需要稍微解释一下用到的“高效能算法”这个词……我没有准备好给出严格的理论体系赋予其正式的含义，况且这篇文章的上下文也不适合这样做……实践中，区分代数级别和指数级别的重要性，要远大于区分可计算与不可计算的重要性……如果硬要制定一些严格的标准，可能会在实践上阻碍有用的算法的研发，因为这些算法要么是未知的，要么理论上与标准不符……无论如何，为鼓励人们去搜寻优秀而实用的算法，很重要的一点是认识到：质疑此种标准的存在价值在数学上是有一定道理的。

埃德蒙兹的“代数级别”正是P所代表的我们能有效计算的问题。正如埃德蒙兹建议的，虽然有必要用正式的方法来定义“是否P=NP”等问题，但我们心中也应该对高效能计算有一种非正式的概念，而这也是我想在本书中表达的一种观点。

科巴姆同样独立地定义了P，并讨论了为什么这个概念很有用。

有很多原因让类型P成为一个自然而然的概念。首先，如果我们对各种通用类型的计算机器分别做一个形式化的表述，会发现总是离不开几个相同的定义明确的函数。据此，我们能给出一个数学的表征P，并相信它能正确地表征那些定义得不那么正式的类别。

和可计算性的定义一样，类型P并不依赖于计算模型的特定细节。

科巴姆也提醒人们注意：

这个问题让人想起如何形式化地定义“效率”这个概念。虽然二者很明显有关联，但是强调的方面不同，这里主要关注的是计算过程的物理方面。

科巴姆也许认识到将来可能出现不属于他所说的类型P的计算模型。随机化和量子计算模型的研发表明，我们也许无法对高效能计算有一个固定的概念。

之后在1971年，斯蒂芬·库克发表的论文定义了NP（即我们能很快验证的问题）、P/NP问题，以及第一个NP完全问题。一年后理查德·卡普在论文中给出了一长串属于NP完全的问题。

1972年，IBM的T. J. 华生研究中心召开了一次有关计算机的计算复杂度的座谈会，这次会议主要因为卡普的论文而被世人记住。组织者在会议结束时安排了小组讨论，探讨这个领域的未来发展。其中一个问题是：“如何把原来零散的下确界结论以及某些算法整合起来，发展成一个更加统一的理论？”对于这个问题的答案，包括卡普本人在内的小组成员都没太有把握，只是模糊地感觉到它可能与库克和卡普的论文有关，与P、NP、可归约性以及之后的NP完全性概念等有关。

卡普意识到他们需要为这个新领域起个好名字：

“计算复杂度”这个名字太宽泛了，它包括了布卢姆和其他人的工作，而现在我们还没法把他们的工作涵盖进来；“混凝土计算复杂度”听起来好像土木工程的分支¹；“计算机计算的复杂度”听起来又不是很准确。

_{1 concrete除了“实际”还有“混凝土”的意思。——译者注}

后来这个领域就叫做计算复杂度。P/NP问题的重要性很快显现，抢尽了这个领域其他研究方向的风头。抽象复杂度给人的感觉更不靠谱了。连曼纽尔·布卢姆本人也改变了研究方向，开始转攻密码学和程序检验。布卢姆因其在20世纪60、70和80年代所做的广泛研究而获得1995年的图灵奖。很多年后，当被问及他在20世纪70年代改变研究方向的原因时，布卢姆简单地答道：“库克是对的。”