如果“P=NP”得到证明，意味着什么？ 第1页

注：这篇文章写的略夸张，因为即使证明了P=NP，我们可以将一个复杂度为指数的算法变成一个复杂度为多项式的算法也并不能说明这个多项式算法很快。即使同是多项式算法，因为非确定型图灵机在现实中是不存在的，在计算机上运行时也不能认为他们“同样容易”。但这篇文章写的很有意思，大家不妨一看。

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

M67写了一篇文章很好的阐述了P=NP所可能带来的影响：

引用自：

在计算机复杂度理论中，P问题指的是能够在多项式的时间里得到解决的问题，NP问题指的是能够在多项式的时间里验证一个解是否正确的问题。虽然人们大多相信P问题不等于NP问题，但人们目前既不能证明它，也不能推翻它。P是否等于NP是计算机科学领域中最突出的问题，在千禧年七大难题中排在首位。科学家们普遍认为P≠NP是有原因的。让我们来看一看，如果哪一天科学家证明了P=NP，寻找一个解和验证一个解变得同样容易，那这个世界将会变得怎样？

已知的NPC难题将全部获解，这将瞬间给各个科学领域都带来革命性的进展。整数规划、01规划、背包问题全部获解，运筹学将登上一个全新的高度；数据库的串行化、多处理器调度等问题也随之解决，大大提高了计算机的性能。同时，空当接龙、扫雷、数独等经典游戏也由于获得了多项式的算法而在很大程度上失去了意义。
算法研究方向将发生全面转移。对算法的研究可能会转向围棋等NP-Hard问题。算法设计的学问与“NP问题统一解”的关系正如小学应用题与列方程解题的关系一样，将成为一种纯粹锻炼思维的游戏。

一些新型的自动编程语言将出现，并将逐渐取代传统的编程语言。这种新型编程语言扮演着一个“判定性/最优化问题万能解决器”的角色。在新的编程语言中，你只需要用代码指明输入数据与输出数据的关系，而无需关心计算输出数据的步骤。只要这种关系是多项式时间内可计算的，编译器将自动找到解法。在新型编程语言的支持下，人们唯一需要考虑的是，如何把实际问题转化成数学模型。

利用Occam剃刀原理，困扰人类已久的自然语言处理问题将被一举攻破。只要提供足够多的语言文字材料，计算机将很快掌握这门语言，并反过来为语言学提供新的科学体系。考虑这样一个最优化问题：输入一大批语句样本，它们有的符合语法，有的不符合语法；寻找一个最简单的算法，将这些语句输入这个算法时，算法能正确得出它是否符合语法。显然，这个问题本身是NP的（当然前提是该算法是多项式的），因此计算机可以在多项式时间内找到能判定语法正误的最简算法。我们有理由相信，这个算法也就是人类头脑中正在使用的算法，因此它能够适用于所给材料之外的其它语句，并具有自我学习的功能。分词技术、手写识别、语音朗读、语音识别等难题在一瞬间全部攻破。
很可能计算机给出的自然语言处理算法完全不同于传统语言学的那一套方法，因此传统语言学本身将受到极大的冲击。字、词、句的概念很可能被重新界定，词类、句式的概念有可能被完全颠覆。

类似地，所有人工智能问题都将得到解决。我们只需要向计算机提交足够多的情境以及与之对应的正常人反应，计算机就可以找出一种能正确生成出这些反应的最简算法，并且由我们的Occam剃刀假设，这种算法能够适用于更广的范围，完全模仿人类的行为。在网络上，再没有任何办法能够把计算机和人区别开来。验证码将变得毫无意义。
计算机不仅能轻易通过图灵测试，还能精确地模仿某一个特定的人。如果你能把某个人的网络聊天记录全部搜集起来，把这个人和网友们的对话全部递交给计算机，计算机将会很快学会如何模仿这个人。网络的身份鉴定将变得相当困难，很可能不得不借助一些物理方式。

数学证明可以完全交给计算机来处理。寻找一个反例和验证一个反例变得同样简单，一切错误的猜想都将瞬间被推翻。事实上，寻找一个数学证明和验证一个证明的正确性也变得同样简单，因此一切正确的命题也能够瞬间找到一个最简的证明。困扰人类数个世纪的数学猜想将逐一获解。数学领域内部将掀起一次革命，数学研究真正成为了一门“提出问题的艺术”而不再是“解决问题的艺术”。数理逻辑等底层研究，以及开创数学新分支并将其形式化，将成为数学研究的主流方向。
类似地，一切具有解释性并可以形式化的科学都可以借助计算机寻求现象的最佳解释方案。物理学、化学、经济学、心理学等学科都将会受到不同程度的影响。

md5算法不再有效，判定一个串的md5是否等于给定值与寻找一个md5等于给定值的串一样轻松。RSA算法也不再有效，寻找一个质因子和判断整除性也变得一样简单。事实上，发明任何新的密码算法都是徒劳——计算机可以根据一大批明文密文样本推算出生成密文的算法（只要这个算法是多项式的）。现有的密码学体系彻底崩溃。理论上不具有可预测性的一次一密协议成为唯一安全的密码协议。但人们很快注意到，密码本本身的生成也不能依赖于任何伪随机数算法，必须完全借助于物理算法。从这个角度来说，纯机器的密码协议将不复存在，任何身份验证手续都必须借助物理手段。互联网可能会变得非常不可靠。

本人对复杂度理论涉猎不深，并且叙述颇有些夸大其辞，欢迎网友们探讨、指正、争论和补充。
本文部分参考一篇牛文，已上传至我的空间，强烈建议大家膜拜：http://www.matrix67.com/data/average.ps

那我就不用读PhD了，直接转行算了……（想想其实也很不错呢 >_<

我导师估计也要失业了

而且目测整个欧美学术圈theory组暂时都没什么正事可以做了，大部分和计算复杂性相关领域的研究都失去了意义

之前发的什么Godel奖、Nevanlinna奖大多数也都是废纸了，什么Probabilistically Checkable Proof，什么Unique Games Conjecture这些所谓的重要研究都是nonsense了

不过数学界的机械化证明目测就要成为主流（这么看其实大部分数学家也要失业了？

（我在原答案中不假思索地随手敲出了上面这句话，但实际上这是不对的，即使P=NP也未必是机械化证明成为主流，没有任何证据证明数学命题的证明属于NP范畴，而且就算我们有多项式算法判断一个数学命题的正确与否，so what？根本不能和找到一个证明的重要性和意义相提并论。

然而我意识到我写这句话是受到了很多其他科普文章的影响，所以我现在觉得解释一下这件事情很重要，说三遍：

上面这句话是不对的，没有任何证据表明判断数学命题正确与否属于NP范畴，更何况判断一个数学命题正确与否根本比不上找出一个证明

上面这句话是不对的，没有任何证据表明判断数学命题正确与否属于NP范畴，更何况判断一个数学命题正确与否根本比不上找出一个证明

上面这句话是不对的，没有任何证据表明判断数学命题正确与否属于NP范畴，更何况判断一个数学命题正确与否根本比不上找出一个证明）

当然以上都是相关专业领域，对于普通民众来说，

说不定人类就要进入一个新时代了

我也很难想象以后的生活，毕竟信仰崩塌了再重建是非常辛苦的，

但普通人的生活也会在短时间内有翻天覆地的变化应该是肯定的了。