P=NP后果会怎样？

姜咏江

计算机科学的世界公开难题最重要的是P versus NP问题。科学界争论了几十年P类问题是否就是NP类问题，到了2017年这个问题应该终结了。最终的结论应该是P=NP。

中国计算机兼数学科学家用限位数理论，破解了SAT问题隐藏在繁云复杂子句中的密码，找到了制约每个逻辑变量取值的条件，厘清了k是不变的常数，合取范式k-CNF最多能够有个不同子句的事实。这就等于告诉了人们，以子句做为操作对象的计算机处理过程，对每个变量不会超过这个k阶多项式所表达的有限时间。

作者不仅从理论上论证了用“消去子句”的方法，可以在O(n^k+1)算法时间复杂度获得SAT的满足解，而且成功地设计出3-SAT“子句消去法”求出满足解计算机程序，通过验证，证实了子句消去法理论的正确性与可靠性。

SAT问题是NP_complete问题中最基本的题目，其它的NP_complete问题基本都是在SAT问题的基础之上建立起来的。根据P与NP问题公认的观点，只要有一个NP_complete问题有多项式时间算法，那么就可以断定P=NP。如今，我们找到了SAT问题的多项式时间复杂度的算法，因而可以说P=NP成立了。P=NP的后果如何？看看国外的P与NP问题的专家们都是怎样认为的吧。

在英文维基百科的P versus NP problem中，关于P=NP的后果，有这样的阐述：

If P = NP, then theworld would be a profoundly different place than we usually assume it to be.There would be no special value in "creative leaps," no fundamentalgap between solving a problem and recognizing the solution once it's found.

—ScottAaronson, MIT

如果P=NP,那么世界上必然有一个与我们平常认识不同的地方。创造性的飞跃没有了特殊的价值，在解决问题和首次找到问题解之间没有了差距。

                                                                      ——斯科特.阿若森  麻省理工学院  

A proof that P= NP could have stunning practical consequences, if the proof leads toefficient methods for solving some of the important problems in NP. Itis also possible that a proof would not lead directly to efficient methods,perhaps if the proof is non-constructive, or the size of thebounding polynomial is too big to be efficient in practice. The consequences,both positive and negative, arise since various NP-complete problems arefundamental in many fields.

如果一个证明导致NP领域许多重要的问题获得有效的解决方法，那么P=NP的证明后果是惊人的。这个证明可能不是直接提供的有效方法，也许这个证明是非建设性的，或者实际中多项式时间的边界太大，但是无论如何， NP完全问题证明的结果在许多领域中都是基础性的。

   还有，如果P=NP,那么基于计算复杂度的密码学是没有用处的。internet和电子商务都面临危险。

也许国外的专家们过于夸大了P=NP的重要性。但无论如何，我敢肯定，P=NP。

2017-5-11