NP猜想（一） (4-2)

还有一些问题，无论其是否能够在多项式时间复杂度内求解，至少我们知道如果随便给出一个可能的解，我们可以在多项式时间复杂度内验证其是否为所求的解。这类问题我们称之为“NP类问题”。比如前面的例子（3），我们随便猜测一组逻辑变量的组合，就可以通过P(n)次逻辑运算判定其结果是否为假，如果是，那么我们就确定这个逻辑表达式不是重言表达式。因此，（3）中的问题虽然我们还没有找到一个多项式时间复杂度的算法，不知道它是否属于“P类问题”，但是我们很确定它一定属于“NP类问题”。

之所以要研究一个问题是否有多项式时间复杂度的算法，是因为多项式时间复杂度的计算量增长速度相对来说算是“慢”的，随着n的增大，其计算量远远小于O(2ⁿ) 、 O(n！) 、 O(nⁿ) 等时间复杂度问题。比如很有名的大整数质因数分解问题，给出一个2048位的二进制整数，要找到它的某个质因数，一般情况下穷尽全世界的计算能力也不能在100年内完成这个求解计算过程；但是如果我给出一个质数，却可以用普通的计算机在几秒钟时间以内确定这个质数是否是这个2048位二进制整数的一个因数。这就是不同时间复杂度在实际计算过程中的差别！

知道了什么是“P类问题”，什么是“NP类问题”，我们就很容易知道，全部的“P类问题”都属于“NP类问题”，也就是“NP类问题集合”⊇ “P类问题集合”。这是显然的，一个问题可以在多项式时间复杂度内求解，当然可以在多项式时间复杂度内验证。但是反过来，一个可以在多项式时间复杂度内验证的问题是否一定能够通过多项式时间复杂度的算法求解呢？也就是说，是否全部的“NP类问题”都属于“P类问题”呢？这就是著名的“NP=P”问题。如果答案为“是”，那就意味着“NP类问题集合”=“P类问题集合”；如果答案为“否”，那就意味着“NP类问题集合” ⊃ “P类问题集合”，但不相等。

如果“NP=P”，这个结果对我们这个世界的影响是很大的。这意味着任何一个原来找不到“P类算法”的NP类问题都可以找到相应的“P类算法”了。比如刚才说的大整数的质因数分解问题，就成为了P类问题。这意味着刚才例子中2048位的二进制大整数可以用一台普通电脑在几秒钟甚至更短的时间完成其质因数分解，那么被广泛应用的RSA加密算法就彻底失效了。我们大量的银行数字证书、网站SSL加密都不再安全，人类必须要寻找新的、更强的加密算法。

同时，这也意味着很多原来通过计算很难解决的大量问题都可以通过算法优化而轻松得到解决了。如果NP=P，那么我们就可以更好地预测天气，更容易通过氨基酸序列来预测蛋白质结构，更好的确定计算机芯片上最有效的晶体管布局，更优的完成物流交通调度，......。

如果“NP≠ P”，对我们这个世界的影响很小，或者说对实际生活几乎没有什么影响。可是，迄今为止还没有谁能给出这个证明。

这个问题的难度远远超过一般人的想象。目前，绝大多数的相关领域科学家（包括数学家、计算理论科学家、IT行业资深算法研究人员等）都认为“NP≠ P”，所以，我们可以暂时先松口气，不用太担心“NP=P”给我们日常生活带来的影响。

二、什么是NPC问题？以及第一个NPC问题

虽然我们还不知道NP是否等于P，但也不是在这方面的研究完全没有进展。早在1971年，多伦多大学计算复杂理论教授斯蒂芬·库克就在其著名论文《定理证明过程的复杂性》（《The Complexity of Theorem - Proving Procedures》）中明确提出了人们一直怀疑其是否存在的一类问题——NPC问题（NP完全问题），并给出了第一个NPC问题的证明。这对推动“ NP = P ”问题的解决是一个巨大的贡献。

第三个军械架

定理证明程序的复杂性

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。