SylphReader

From: 再谈“P vs NP”问题
再谈“P vs NP”问题曾经写过一篇文章，表达对计算机科学里著名的 “P vs NP” 问题的看法。当时正在研究那些东西，由于看透了却不在乎，所以写得特别简略。没想到有人看到那篇文章后，还误以为我没仔细学过复杂度理论，说我是信口开河。我一般懒得谈论这种太理论的问题，身边也很少有人关心，所以后来干脆把文章撤了。没想到最近又遇到有人抓住我删掉的文章，乘机跟我辩论这事。跟上课似的头头是道滔滔不绝，几乎把他本科算法课本上的内容给我背了一遍，却没有显示出任何他自己的思想。说王垠你太武断了，你知不知道 P vs NP 要是解决了，世界将有天翻地覆的变化，多少的计算难题会被解决，非对称加密全都被破解！…… 呃，我真是服了某些人。所以呢，我决定事后把这个问题再详细讲一下，免得以后还要为它费口舌。 “P vs NP” 问题属于计算理论（Theory of Computation）的一部分：复杂度理论。计算理论不止包括复杂度理论，还包括可计算性。如果你没有系统的学习过复杂度理论，我建议你仔细研读一下经典的计算理论教材，比如 Michael Sipser 的『Introduction to the Theory of Computation』。我觉得 Sipser 的书写的不够清晰透彻，但很多学校拿它做教材，好像也没有更好的替代品，所以将就着看吧。 “P vs NP” 真的是重要问题？ “P vs NP” 这个问题有它的理论价值，它是有趣的问题，值得花些时间来了解。但计算机科学界长久以来都严重夸大它的重要性，把一个很普通的问题捧上了天，吹得神乎其神。很多人认为“P vs NP”是计算机科学最重要的问题。Clay 数学研究所甚至悬赏一百万美元解决这个问题，把它叫做数学界的 7 个千年难题之一，跟黎曼猜想并列其中。好几次有人声称解决了“P vs NP”，上了新闻，闹得舆论沸沸扬扬，小编们吹得好像世界要天翻地覆了一样，把他们追捧为天才苦行僧，后来却又发现他们的结果是错的…… 如果你真的理解了“P vs NP”的内涵，就会发现这一切都是闹剧。这个问题即使得到解决，也不能给世界带来很大变化。解决这个问题对于现实的计算，作用是微乎其微的。不管 P 是否等价于 NP，我们遇到的计算问题的难度不会因此有任何改变。在我看来，“P vs NP” 根本没有资格跟黎曼猜想一起并列于“千禧年问题”。我倒是希望有人真的解决了它，这样我们就可以切实的看到这有什么意义。 “P vs NP” 不是愚蠢的问题，但计算机科学界夸大它的重要性的做法，是非常愚蠢的。什么是多项式时间？真正重要的数学问题被解决，应该对现实世界具有强大的作用。这种作用可以是“潜在的”，它的应用可以发生在很久以后的将来，但这必须能够被预见到。数学家们把这叫做“applicable result”。否则这个数学问题就只能被叫做“有理论价值”，“有趣”，而不能叫做“重要”。即使所谓“纯数学”，也应该有可以预见的效果。很多数学家都明白黎曼猜想（Riemann hypothesis）的重要性。大数学家希尔伯特说过：“如果我沉睡了三千年醒过来，我的第一句话会是‘黎曼猜想被解决了吗？’” 如果希尔伯特还在世，他会对解决“P vs NP”有同样的渴望吗？我觉得不会。实际上，很多数学家都觉得“P vs NP”的重要性根本没法和黎曼猜想相提并论，因为我们预见不到它会产生任何重要的效果。很多人提到“P vs NP”总是跟你吹嘘，P 如果等于 NP，世界将有天翻地覆的变化：许许多多我们以前没法办到的事情，都将成为现实。非对称加密技术会被破解，生物化学将得到飞跃…… 这些人都忽略了一个重要的问题：什么是多项式时间。盲目的把“多项式”等同于“容易”和“高效”，导致了对 “P vs NP” 重要性的严重夸大。 n^100 是不是多项式？是的。n^(100^100) 也是多项式。时间复杂度为 n^(100^100) 的算法，能用吗？所以即使 P=NP，你需要的计算时间仍然可以是直到宇宙毁灭。说到这里，又会有人跟我说你不懂，当 n 趋近于无穷的时候，非多项式总会在某个时候超越多项式，所以当 n “足够大”的时候，多项式时间的算法总是会更好。很可惜，“无穷”对于现实的问题是没有意义的。任何被叫做“重要”的问题，都应该在合理的时间内得到结果。我们关心的要点不应该是“足够大”，而是“具体要多大”。精确的量化，找到实际可以用的区间，这才是一个合格的科学家应该具有的思路。计算机科学里，大 O 表示法泛滥成灾，只看最高次幂，忽略系数和常数项，也是常见的误区。我也曾经沉迷于如何把 O(n^3) 的算法降低到 O(n^2.9)，现在回头才发现当年是多么的幼稚。 “多项式时间”这个概念太宽泛太笼统。以如此笼统的概念为基础的理论，不可能对现实的计算问题产生意义。我们关心的不应该仅仅是“是否多项式”，而是“具体是什么样的多项式”。多项式的幂，系数，常数项，它们的不同都会产生重大的差异。这就是为什么“P vs NP”没有很大意义，因为 P 本身太笼统，其内部的差异可以是天壤之别。研究“P vs NP”就像研究“男人 vs 大猪蹄子”一样笼统而不严谨。与其试图笼统的证明 P 是否等价于 NP，还不如为具体的问题想出高效的算法。其它质疑 P vs NP 价值的人很多人认为我质疑 P vs NP 的价值是狂妄和信口开河，然而我并不是第一个质疑它的人。很多人对 P vs NP 都有类似的疑惑，但因为这个问题的地位如此之高，没人敢站出来。只要你开口，一群人就会居高临下指责你基础课程没学好，说你眼界太窄…… 再加上那一堆纷繁复杂基于图灵机的证明，让你有苦说不出。由于这个原因，我从来没敢公开表达我的观点，直到我发现 Doron Zeilberger 的这篇文章。Zeilberger 是个数学家，Rutgers 大学的数学系教授。在那之前他开了个玩笑，戏称自己证明了 P=NP，还写了篇像模像样的论文。在文章里他告诫大家：不要爱上你的模型（Don’t Fall In Love With Your Model）。他这句话说到了我心里。你还能在网络上找到其它学者对“P vs NP”的质疑，比如这篇来自于一位专业研究计算理论的学者： Is P=NP an Ill Posed Problem? 我觉得他讲的也很在理。正是在这些人的鼓舞之下，我冒着砖头写出了之前对 P vs NP 的质疑。只言片语里面，融入了我多年的深入学习，研究和思考。我希望理性的计算机科学工作者能够理解我在说什么，反思一下对 P vs NP 的理解。我希望计算机专业的学生能够理解 P vs NP 理论，但不要沉迷其中。这并不是一个值得付出毕生精力去解决的问题。当然所有这些都是我个人的观点，我没有强求任何人接受它们。没人想抢走你们的玩具，但不要忘了，它只是玩具。

再谈“P vs NP”问题

曾经写过一篇文章，表达对计算机科学里著名的 “P vs NP” 问题的看法。当时正在研究那些东西，由于看透了却不在乎，所以写得特别简略。没想到有人看到那篇文章后，还误以为我没仔细学过复杂度理论，说我是信口开河。我一般懒得谈论这种太理论的问题，身边也很少有人关心，所以后来干脆把文章撤了。

没想到最近又遇到有人抓住我删掉的文章，乘机跟我辩论这事。跟上课似的头头是道滔滔不绝，几乎把他本科算法课本上的内容给我背了一遍，却没有显示出任何他自己的思想。说王垠你太武断了，你知不知道 P vs NP 要是解决了，世界将有天翻地覆的变化，多少的计算难题会被解决，非对称加密全都被破解！……

呃，我真是服了某些人。所以呢，我决定事后把这个问题再详细讲一下，免得以后还要为它费口舌。

“P vs NP” 问题属于计算理论（Theory of Computation）的一部分：复杂度理论。计算理论不止包括复杂度理论，还包括可计算性。如果你没有系统的学习过复杂度理论，我建议你仔细研读一下经典的计算理论教材，比如 Michael Sipser 的『Introduction to the Theory of Computation』。

我觉得 Sipser 的书写的不够清晰透彻，但很多学校拿它做教材，好像也没有更好的替代品，所以将就着看吧。

“P vs NP” 真的是重要问题？

“P vs NP” 这个问题有它的理论价值，它是有趣的问题，值得花些时间来了解。但计算机科学界长久以来都严重夸大它的重要性，把一个很普通的问题捧上了天，吹得神乎其神。

很多人认为“P vs NP”是计算机科学最重要的问题。Clay 数学研究所甚至悬赏一百万美元解决这个问题，把它叫做数学界的 7 个千年难题之一，跟黎曼猜想并列其中。

好几次有人声称解决了“P vs NP”，上了新闻，闹得舆论沸沸扬扬，小编们吹得好像世界要天翻地覆了一样，把他们追捧为天才苦行僧，后来却又发现他们的结果是错的……

如果你真的理解了“P vs NP”的内涵，就会发现这一切都是闹剧。这个问题即使得到解决，也不能给世界带来很大变化。解决这个问题对于现实的计算，作用是微乎其微的。不管 P 是否等价于 NP，我们遇到的计算问题的难度不会因此有任何改变。

在我看来，“P vs NP” 根本没有资格跟黎曼猜想一起并列于“千禧年问题”。我倒是希望有人真的解决了它，这样我们就可以切实的看到这有什么意义。

“P vs NP” 不是愚蠢的问题，但计算机科学界夸大它的重要性的做法，是非常愚蠢的。

什么是多项式时间？

真正重要的数学问题被解决，应该对现实世界具有强大的作用。这种作用可以是“潜在的”，它的应用可以发生在很久以后的将来，但这必须能够被预见到。数学家们把这叫做“applicable result”。否则这个数学问题就只能被叫做“有理论价值”，“有趣”，而不能叫做“重要”。即使所谓“纯数学”，也应该有可以预见的效果。

很多数学家都明白黎曼猜想（Riemann hypothesis）的重要性。大数学家希尔伯特说过：“如果我沉睡了三千年醒过来，我的第一句话会是‘黎曼猜想被解决了吗？’” 如果希尔伯特还在世，他会对解决“P vs NP”有同样的渴望吗？我觉得不会。实际上，很多数学家都觉得“P vs NP”的重要性根本没法和黎曼猜想相提并论，因为我们预见不到它会产生任何重要的效果。

很多人提到“P vs NP”总是跟你吹嘘，P 如果等于 NP，世界将有天翻地覆的变化：许许多多我们以前没法办到的事情，都将成为现实。非对称加密技术会被破解，生物化学将得到飞跃……

这些人都忽略了一个重要的问题：什么是多项式时间。盲目的把“多项式”等同于“容易”和“高效”，导致了对 “P vs NP” 重要性的严重夸大。

n^100 是不是多项式？是的。n^(100^100) 也是多项式。时间复杂度为 n^(100^100) 的算法，能用吗？所以即使 P=NP，你需要的计算时间仍然可以是直到宇宙毁灭。

说到这里，又会有人跟我说你不懂，当 n 趋近于无穷的时候，非多项式总会在某个时候超越多项式，所以当 n “足够大”的时候，多项式时间的算法总是会更好。很可惜，“无穷”对于现实的问题是没有意义的。任何被叫做“重要”的问题，都应该在合理的时间内得到结果。

我们关心的要点不应该是“足够大”，而是“具体要多大”。精确的量化，找到实际可以用的区间，这才是一个合格的科学家应该具有的思路。计算机科学里，大 O 表示法泛滥成灾，只看最高次幂，忽略系数和常数项，也是常见的误区。我也曾经沉迷于如何把 O(n^3) 的算法降低到 O(n^2.9)，现在回头才发现当年是多么的幼稚。

“多项式时间”这个概念太宽泛太笼统。以如此笼统的概念为基础的理论，不可能对现实的计算问题产生意义。我们关心的不应该仅仅是“是否多项式”，而是“具体是什么样的多项式”。多项式的幂，系数，常数项，它们的不同都会产生重大的差异。

这就是为什么“P vs NP”没有很大意义，因为 P 本身太笼统，其内部的差异可以是天壤之别。研究“P vs NP”就像研究“男人 vs 大猪蹄子”一样笼统而不严谨。与其试图笼统的证明 P 是否等价于 NP，还不如为具体的问题想出高效的算法。

其它质疑 P vs NP 价值的人

很多人认为我质疑 P vs NP 的价值是狂妄和信口开河，然而我并不是第一个质疑它的人。很多人对 P vs NP 都有类似的疑惑，但因为这个问题的地位如此之高，没人敢站出来。只要你开口，一群人就会居高临下指责你基础课程没学好，说你眼界太窄…… 再加上那一堆纷繁复杂基于图灵机的证明，让你有苦说不出。

由于这个原因，我从来没敢公开表达我的观点，直到我发现 Doron Zeilberger 的这篇文章。Zeilberger 是个数学家，Rutgers 大学的数学系教授。在那之前他开了个玩笑，戏称自己证明了 P=NP，还写了篇像模像样的论文。在文章里他告诫大家：不要爱上你的模型（Don’t Fall In Love With Your Model）。他这句话说到了我心里。

你还能在网络上找到其它学者对“P vs NP”的质疑，比如这篇来自于一位专业研究计算理论的学者：

Is P=NP an Ill Posed Problem?

我觉得他讲的也很在理。正是在这些人的鼓舞之下，我冒着砖头写出了之前对 P vs NP 的质疑。只言片语里面，融入了我多年的深入学习，研究和思考。

我希望理性的计算机科学工作者能够理解我在说什么，反思一下对 P vs NP 的理解。我希望计算机专业的学生能够理解 P vs NP 理论，但不要沉迷其中。这并不是一个值得付出毕生精力去解决的问题。

当然所有这些都是我个人的观点，我没有强求任何人接受它们。没人想抢走你们的玩具，但不要忘了，它只是玩具。