2009-11-17 14:25| 
59 Comments | 本文内容遵从在计算机复杂度理论中，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
看不懂。。
那篇牛文怎么看？
不怎么理解
可以通过判断对方有没有健全的感情之类的方式。。
不过对人来说貌似负担很大，而且可能误判
不过也就是说P很有可能不等于NP了？
到时候就是共产主义了......
强势插入前十,全身而退~
可能这就是现在CS发展最集中的问题吧，P与NP。但文中可能有点问题的是，即使P=NP能够证明，但对于P问题的多项式算法（如哥德巴赫？），NP的算法只是理论上存在，在现在的架构下还没有发现（也不大可能）吧。穷举出这些的答案可能太过匪夷所思。可能对于更多的问题，P=NP即使成立，实用价值在科研上是毋庸置疑，实际上倒不会像文中那么严重吧。
最后，真的写的很好……MARTIX67大牛真的很强大。小P孩，胡言乱语，博君一笑。
太玄乎了……
感觉NP=P这个问题是不可证的。。。
这也太神奇了,,-_-
原来科幻片和现实之间的断层是在这里
不过是福是祸 谁知道呢
曾几何时一个根号2也让人们觉得及神奇有恐慌
即使P = NP，也不太可能是我们通常意义上的P算法那样简单..所以实用价值未必会很高（也许只是对密码算法有大的突破）
从P=NP的证明，到一个实际计算时间内可以接受的等于NP的P算法还有几个光年的距离........
btw 想证明P=NP不可证明这件事情，证明起来也非常有难度........
[...] This post was mentioned on Twitter by Sunny / é³é³çª and 阳阳猪的 GR Share, Zelong Yu. Zelong Yu said: 技术宅们来围观matrix67雄文： 假如P=NP，世界将会怎样？http://www.matrix67.com/blog/archives/2552 [...]
光年远的距离。。。。
我只是看看
尋找證明反例與證明算法最簡不可規約至coNP完全，命題正確性（基於任何包含一堦邏輯的形式系統）Turing不可判定。
让我想到了哥德尔~
说点我知道的：md5跟np没关系吧，而且现在md5已经存在安全问题了。rsa同样也是没有证明与np问题等价，只是人们*相信*rsa的安全性基于大数分解（可以参看http://en.wikipedia.org/wiki/Rabin_cryptosystem）
还是希望P≠NP,否则很多人都要失业了，哈哈。
这个说的太夸张了，首先可能P=NP的证明就不是构造性的，就跟纳什均衡定理一样，证明均衡点存在不意味着你能找得到它。所以NPC问题的多项式算法可能还是找不到，所有问题就依然存在...
这些大约都是在人们努力证明P=NP的过程中发生的。。而不是之后。
这些大约都是在人们努力证明P=NP的过程中发生的。。而不是之后。
反正这个过程很漫长就是了。。甚至无解。
可能正确。但是从直观主义判断，就算P=NP，也必定会有新的原理阻碍等价变换的进行。。。或许在数学里也有某种形式的熵增原理？
所有人工智能问题都将得到解决。
============================
由于哥德尔不完备，算法所处于的系统内必然存在不可判定的问题。譬如做图灵测试的时候问对方一系列的停机问题，对于计算机，充分多的有限次提问内必然会有无法判定情况发生。
很有意思的话题，我想一部分NP可能是可以转换为P的，但不可能证明NP=P
虽然我没看完，可是好深奥
我想这辈子知道结果。。。。
只要有量子力学在，自然科学依然不会在P=NP面前倒下
量子力学为未来提供了不可预知性
可是如果这个多项式的次数特别高，比如10000次，就已经无法承受了
"诈欺游戏",建议博主看看,个人认为博主会喜欢看的,虽然本片对博主的智商来说是小儿科
其实复杂性分层问题里面，P \neq NP只是一个比较强的假设，还有其他的弱的假设，并不是说P \neq NP才是最重要的,只是这个问题比较基本，也比较久远。即使我们最终证明了P=NP，也并不意味着我们在实际生活中可以直接使用。举两个例子，Khachiyan的椭球算法是多项式时间的，但是实际上的效率是远远低于单纯性的，也是不可接受的。即使Karmarkar的内点法在实际运行的效果也不乐观。AKS的质数检测算法也是多项式的，但是实际效率也远远低于随机算法。人们往往看到多项式算法就觉得问题已经可以达到被任意蹂躏的地步了，可是实际上还是差很远的。90年代以来出现的pcp理论和smooth analysis都是对问题复杂性新的认识。只是从P和NP的角度来看问题，已经过时了。NP类的概率刻画更加接近现实，虽然远不如非确定性图灵机直白。
“寻找一个反例和验证一个反例变得同样简单”，这个“同样简单”的定义应该是说同样都是多项式算法的。但是O(n)和O(n^10)你会认为他是同样简单的么？http://rjlipton.wordpress.com/
这个blog我一直都在看，文章很精彩。大家去看看大师是怎么样理解P vs NP问题的。
有些真是夸大了.文章里说的很多都是是不可判定或者NP-H的
同时，空当接龙、扫雷、数独等经典游戏也由于获得了多项式的算法而在很大程度上失去了意义。
--------------------
这话是不能乱说的，这些游戏本来就是开发人脑的，你用电脑能轻易去解决它们并不代表它们就失去了意义
什么叫多项式时间？？？
让好莱坞拍个电影，就叫 P=NP 大概不会有很多人能看懂
Orz Martrix67 神牛
明天就NOIP2009了
好像最近有人证明纳什均衡的求解是NP的，matrix大牛对此有什么评论吗？
很难理解到啊!
即便P=NP，有可能短时间也找不到有效的算法啊，比如可能是n^1000什么的……记得Richard Lipton还是谁写文章讨论过N种可能~
如果真有有效算法求解NPC问题的话，个人认为最重要的后果，如博主所说，一是机器全面取代数学家做定理证明，二是破解密码变得和验证密码一样简单……
楼层: 34楼 | 2009-11-19 3:25 | clock 说：
“寻找一个反例和验证一个反例变得同样简单”，这个“同样简单”的定义应该是说同样都是多项式算法的。但是O(n)和O(n^10)你会认为他是同样简单的么？http://rjlipton.wordpress.com/
这个blog我一直都在看，文章很精彩。大家去看看大师是怎么样理解P vs NP问题的。
-----------
握手~
顺便请教，什么是“NP类的概率刻画”？是指NP = PCP[O(log n),O(1)]这个结果吗？
不太对吧，就算NP=P，那么解决NP问题的那个多项式算法的复杂度也估计会有一个巨大的常数，很可能还不如指数算法快呢。举个例子，正则表达式匹配是一个O(N)时间的问题，但是常用算法则是回溯法。
另外，自然语言的问题通常都不是NP问题。数学证明不一定是NP问题，很可能是不可判定问题。RSA的大数分解还没有被证明为是NP问题，
那篇文章是E文的，头晕。。。
那篇文章竟然是E文的，头晕ing...
看看不完备定理吧，这个东西可能是不能被证明或否定的。
38楼有想法……
我想，这也许会出现数的连续统那种情况吧。
不知道那篇文章怎么样，看起来引用次数很一般
发个pdf版的吧，在我的google doc上
http://docs.google.com/fileview?id=0B52eVLlW9bdxMTE4N2RlNTgtM2MzZS00YmQ2LWJiMjQtMTExZmNjN2VhYjcw&hl=en
这个好。连PGP也渣掉了。
[...] P = NP 的现实后果，可以参阅这篇笔调略显夸张的文章。2002 年对该领域专家的一次调查显示，相信 P = NP 以及 P ≠ NP [...]
Orz神帖。。。挖坟留名
[...] P = NP 的现实后果，可以参阅这篇笔调略显夸张的文章。2002 年对该领域专家的一次调查显示，相信 P = NP 以及 P ≠ NP [...]
不仅说的夸张，而且不科学，有严重的误导成分，尤其是这句“寻找一个反例和验证一个反例变得同样简单，一切错误的猜想都将瞬间被推翻”。这最多只能说是对可判定问题上的效率会提高，但是不可判定问题呢？P=NP的影响最多只是对可计算问题，但是在人类科学界不可计算问题多了去了。P=NP并不会让这个世界怎么翻天覆地的。
[...] 联想到去年Matrix67同学的畅想：假如P=NP，世界将会怎样？貌似一切美好的梦想都已经即将成为泡影，不过还好，至少RSA安全了，我还可以继续用它签名。:) By akismet-84672796d5609c33ca4e4cdd52d0b420, on 08/10/2010 at 13:51, under Programing. 标签：CS. 评论暂缺 Post a comment or leave a trackback: Trackback URL. « User Story:这么混，我们能成吗？ [...]
这个真的可以证明吗？好深奥的东西啊！
作者这篇文章有很片面的地方，NP并不是全部问题，而只是更大的一类称作PSPACE也即多项式空间复杂度问题的一部分，所以解决了P=NP，只是说我们目前的一系列NP-complete的问题可以得到求解，而很多PSPACE完全问题（比如说有步数限制的围棋，以及其他很多对抗游戏），即使NP可以被解决，也依然无法得到解决（P是NP的子集，NP是PSPACE的子集，目前我们还无法知道NP是否是PSPACE的真子集）。再往上还有EXPTIME和EXPSPACE问题，所以即使证明了P=NP，还只是在算法学上走了一小步。
再说了，图灵测试基本上不可能只是个NP问题。。。
[...] 假如P=NP，世界将会怎样？ [...]
[...] 假如P=NP，世界将会怎样？ [...]