分享

呵呵，虽然本人对算法不是特别精通，但是最近花了挺多时间在P/NP问题，而且也想到了一个全新的思路，所以今天写一篇关于这个问题的blog，顺便也巩固一下我自己在这方面的认知，如果大家发现本文有任何问题，请指正。

什么是P/NP问题？

P/NP问题可以被认为说整个计算机科学最核心的问题，也是Clay七大千禧年大奖难题之一，首先将给大家介绍一下P/NP问题的四个最核心的概念：

1. NP：由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成，也就是说，NP问题就是那些计算过程比较繁琐，但验证答案却很容易的问题，比如把整数44427进行因数分解，求解过程可能会很费时，但如果告诉你答案是177×251，简单计算即可验证答案是对的，
2. P：其包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题，P问题也就是那些计算起来很容易，利用多项式算法很快能解决的问题，比如求若干个数的乘积。
3. NP完全（Complete）：NP完全问题应该是最不可能被化简为P（多项式时间可决定）的决定性问题的集合，而且NP完全问题之间是可以互相转换的，也就意味着只要一个NP完全问题能在多项式时间内解决，那么所有的NP完全问题都能在多项式时间内解决。
4. NP难（Hard）：在计算复杂度理论中，定义那些至少和NP里面最难的问题一样难的问题为HP难，也就是说，NP难的问题最差也是NP完全这个级别，比如寻找国际象棋或围棋最佳走法（在n乘n棋盘上）是指数时间完全的。

而P/NP问题，就是论证P=NP还是P!=NP：如果P!=NP，也就是有些很容易得到验证的问题不容易被轻松地求解，这样我们的基于非常容易被验证的素数算法的密钥系统将保持完全，在影响方面，虽然这个世界本来是就是假设P!=NP，所以不会出现任何大的变化，但是整个证明的过程将会对其它一些问题的解决会有一定的启发作用，并对整个科技的发展有一定的推动；如果P=NP的话，每个答案很容易得到验证的问题也同样可以轻松求解，同时NP完全的问题也能被轻松地解决，而整个世界将会发生巨变，比如，所有的基于密钥的安全系统将失灵；算法的研究可能会转向围棋等NP难问题；数学证明可以完全交给计算机来处理；所有人工智能问题都将得到解决，并且机器人能完美模拟人类的行为。下图为P=NP和P!=NP被证明之后，计算复杂度领域新的概览：

图1. 概览

如果P!=NP，情况和现在差不多，NP完全和P都是NP的子集，但如果P=NP，P、NP和NP完全是相等，也就意味着所有NP完全的算法都能被快速地解决。

还有，为了方便介绍下面的，稍微介绍一些属于NP完全的算法，比如，著名的旅行商（Travelling Salesman）问题和哈密顿回路（Hamiltonian cycle）和用于测量布尔组合电路效果的布尔可满足性问题（Boolean Satisfiability Problem，简称SAT），下图一些NP完全问题及证明其为NP完全问题的变换流程图。在流程图中，箭头代表的是从何问题变换成另一问题的过程，要注意的是这张图并不代表这些问题的数学关系，事实上任两个本质为NP完全问题都可以以多项式时间变换，这图仅指示可以让研究者较为简单地变换问题的顺序，最源头的是SAT问题。

图2. NP完全问题

HP研究员的论文

图3. Vinay Deolalikar

最近，大家都知道HP研究院Vinay Deolalikar在美国时间8月8号发布一篇希望能证明P!=NP的论文，并在接下来的几天根据读者的反馈做了一定的更新，这里是最新版论文和概要，经过了包括陶哲轩、Richard Lipton和Timothy Gowers等多位顶级大师的审阅和在网上的讨论，发现Vinay Deolalikar的论文有一定的瑕疵，离证明P!=NP还有一定的距离，下面是陶哲轩的原话：“Ultimately, it seems that what Deolalikar has really proven is not that P != NP, but rather that pp != ppp,for which we have a simple half-page proof（最终，似乎Deolalikar真正已经证明不是P!=NP，而是只需半张纸就能证明的PP!=PPP）”

证明逻辑 

简单而言，他首先利用有限模型理论（finite model theory）中对多项式时间的描述，使用到了Moshe Vardi 和Neil Immerman的一个非常精彩的理论：在排序的结构中，一个关系可以定义为一阶逻辑公式加上最小定点（Least Fixed Point）算子，如果这个算子能在多项式时间内被计算。接着，他直接进攻SAT，希望能通过证明属于NP完全问题也是NP里面最难的问题之一的SAT不可能是P，来证明P!=NP，他的方式是：创建一个能编译SAT的排序结构，假设P=NP的话，为了迎合上面提到的理论，SAT会有特定的结构属性，而这些结构属性却和随机SAT的结构有关。总体来说，这个将有限模型理论和Random SAT模型串联起来的思路还是比较新颖。

主要问题 

对于论文的证明，许多人有不同的看法，但有一点非常关键，那就是Neil Immerman在Deolalikar对上面提到那个由他创建的理论的使用方式上面非常有异议。

我的一些想法

对于这个问题，我个人也已经有了一整套新的思路，但现在还成熟，计划在年内将paper投递给《中国计算机学会通讯》，是证明P=NP还是P!=NP，这个先保密。最后，和大家聊聊一下情怀，最近听闻美国这个季度的GDP增长为1.6，比较乏力，从这个数据我们可以得出，只要在今后十年我们能出现一家能超越微软/苹果/谷歌并能领导这个科技发展的企业，再加上我们庞大的人口基数，在经济总量上接近美国不是一个梦想，所以在这个巨大的浪潮当中，我觉得我们不应该选择抱怨、放弃或者求稳，而应该选择行动、坚持和冒险，因为挑战越大，风险越大，人生才会更好玩！

参考资料：

1. 惠普实验室数学家破解计算机科学最大难题
2. 假如P=NP，世界将会怎样？
3. P vs. NP，我们从过去的一周中学到了什么？
4. P/NP问题
5. Hamilton环多项式时间算法的说明
6. NP完全
7. Deolalikar P vs NP paper
8. The P≠NP “Proof” Is One Week Old
9. NP-hard

分享