反驳王垠的P vs NP问题无用论

作者:, 发表于

感谢ppwwyyxx的回复让我思路更清晰。再此总结观点如下(不完全针对王垠的观点):

  1. P vs NP并未希望解决所有算法问题,它提出一个NPC问题是否有多项式算法。后续还有很多工作要做。先提出是否有解,然后根据情况去提速度去优化。这种路径即使在实用逻辑上也没有问题,更甭提这个问题的理论价值。
  2. 王垠主要提出的是NPC即使找到多项式解,但也可能次数相当高,导致毫无意义。这是错误的,因为 a)次数高只是一种可能性,如果非要抬杠的话都不用在次数上做文章,直接在常数项上做文章即可,线性算法也不一定比指数算法效率高;b)事实上,如果真的发现NPC的多项式解法,次数可能并不高。看一下历史上人们发现的算法,多项式次数大部分都在10以内;另外NPC问题之间的归约,导致只要有一个快速算法,其它都有类似的快速算法,绝对不会让多项式次数无限高。
  3. P=NP的证明可能是非构造性的,但这只是一种可能性。还是那句话,P vs NP问题只是一个基础,有非构造性证明,后面可以想构造性证明;有100次方的算法,后面可以优化为10次方的算法。
  4. 如果P!=NP,就认为这个问题实际价值不大,这个太过武断。首先,现实中大部分还没找到快速算法的问题都已被证明是NP-hard,一旦P!=NP,可直接判处这些问题的死刑。比如你在做Google Jam比赛中遇到一个NPC问题就不会挖空心思去搞什么二次方算法了。另外,某些密码学的安全性也有理论保障。
  5. 最后,P vs NP问题在实际应用中可被攻击的一点,并不是多项式的次数问题。而是在实际操作中并不需要完全求解,概率算法和近似算法在大多数情况下已经足够。但概率可解和近似可解性可能也是一个难度与P vs NP问题相同的问题。

————————————————————————————————

王垠写了不少文章,其中有一些说了较多别人做得如何地差,对自己的评价则相当高(我和Google的故事这篇文章是一篇典型,几篇退学的文章类似)。但之前我并不太了解他工作的领域,并不清楚这哥们的真实水平。但这几天他评论的P vs NP问题,恰好是我也熟悉的领域。其评论让我不吐不快,并确定他太刚愎自用。

————————————————————————————————

王垠最近发表了一篇文章,名字叫做《解决问题和消灭问题》,大意是很多难题都是「人造」的,而不是「必然」的。这些问题根本不是问题,不需要去解决,而应该直接忽略或者说消灭它。

这类大而广的结论具有政治正确性,你不可能去驳斥。但王垠同学居然用「P vs NP」举例,认为「P vs NP」就是一个这样没有任何意义的问题。

后面王垠又发表了一篇文章《谈「P=NP?」》,里面主要两个论点是:

  1. 「P=NP?」这问题的错误就在于,它并没有针对我们的实际需要,而是首先假设了我们有「无穷大」的输入,有「无穷多」的时间和耐心,可以让多项式时间的算法「最终」得到优势。「无穷」和「最终」,就是理论家们的杀手锏。 王垠举的多项式的例子是 \(N^{1000000}\) 甚至 \(n^{10^{100}}\)
  2. 「P=NP?」只关心是否「能够找到多项式时间算法」,而不关心是否「能够找到快速的多项式时间算法」。少了「快速的」三个字,也就是说这个多项式算法的复杂度,完全可以是像  \(n^{10^{100}}\) 这样的。所以「P=NP?」的目标,也就是证明是否「能够找到多项式时间算法来解决所有的 NP 问题」,其实对于「找到快速的多项式算法」,一点用都没有。

这两个论点非常有迷惑性,但事实上:

  1. 如果能证明P=NP,对于NP问题找到的算法的确可以像 \(n^{10^{100}}\) 没有任何实际意义,但也可能是 \(N^6\) 。比如素数判定问题在2002年才被找出多项式算法,它的复杂性并未高的离谱,最终改进的结果是 \(N^6\) 。先找到一个解,才能继续谈去优化这个解。
  2. 事实上,如果能证明P=NP,简单的多项式算法更有可能。由于在NP问题之间存在归约关系,所有NP问题都可以归约到一个3-SAT问题,只要3-SAT问题存在一个比较快的解法,其它NP-Hard问题都有一个类似的较快的解法。王垠举的多项式的次数显示他对这个问题缺乏最基本的了解。
  3. N^6和2^N的分界线低于30。
  4. 另一方面,多数理论学家都相信「P!=NP",即NP问题不存在多项式算法,即使 \(n^{10^{100}}\) 级别的算法都没有。而王垠似乎断定P=NP。
  5. 王垠认为一旦证明出P!=NP,这结论更没有用,因为还存在很多问题在P和NP之间,不确定其复杂性。它后面这个结论是对的,但P和NP之间的问题更多是「虚构」而不是实际的问题。在现实中遇到的绝大多数还没被找到多项式算法的问题,都已经被证明是NP-hard。一旦证明P!=NP,这些问题都将直接被证明不存在多项式解!

王垠介绍P和NP问题为确定型图灵机和非确定型图灵机可在多项式时间内解决的问题,这只是一种形式上的定义。更本质以及更容易理解的定义应该是下面这个

  1. P是指普通计算机可以快速求解的问题(的集合),这里快速求解指多项式时间内。
  2. NP问题指普通计算机可以快速验证解的正确性的问题。

举个例子,比如说大数分解问题,即要将一个很大的数分解为质因子的乘积。这个问题目前还没找到多项式算法,所以无法确定是否属于P。

但如果你一旦知道大数分解的结果,然后判断这个结果是否正确,则是一件非常简单的事情,只需要把质因子乘起来看看是否等于大数即可。所以大数分解就是一个NP问题。

从这个角度看,NP的思想已经不限于算法领域,它有更深层次的哲学含义。比如我们平时读论文时,验证别人证明方法往往比较容易,那么是否有一种思考的方法,能快速求解全天下所有问题呢?其它一些有趣的讨论见What if P = NP?

所以我认为P vs NP问题是数学领域有史以来最重要的问题之一,它成为Clay研究所公布的千禧七大问题之一绝对是实至名归。

如果王垠能从概率算法和近似算法(这两个是更实用的算法,但其复杂性也是理论界存在多年的疑难问题)这类实用算法的角度来攻击P vs NP,我会更尊重他。

Q.E.D.


上一篇:What if P = NP?2007年3月23日
Princeton的Sanjeev Arora和Boaz Barak最近写了一本计算复杂性方面的书:Complexity Theory: A Modern Approach,其初稿提供下载,并承诺出版后也会继续保留——要是

下一篇:完美洗牌问题线性算法的两篇论文2013年11月28日
之前讨论过的完美洗牌问题的两篇论文,实现线性算法,常数空间。


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。