CMP设计分享 http://blog.sciencenet.cn/u/accsys 没有逆向思维就没有科技原创。 不自信是科技创新的大敌。

博文

P=NP后果会怎样?

已有 25635 次阅读 2017-5-11 13:04 |个人分类:SAT问题|系统分类:科研笔记| 子句消去法

P=NP后果会怎样?

姜咏江

计算机科学的世界公开难题最重要的是P versus NP问题。科学界争论了几十年P类问题是否就是NP类问题,到了2017年这个问题应该终结了。最终的结论应该是P=NP

中国计算机兼数学科学家用限位数理论,破解了SAT问题隐藏在繁云复杂子句中的密码,找到了制约每个逻辑变量取值的条件,厘清了k是不变的常数,合取范式k-CNF最多能够有个不同子句的事实。这就等于告诉了人们,以子句做为操作对象的计算机处理过程,对每个变量不会超过这个k阶多项式所表达的有限时间。

作者不仅从理论上论证了用“消去子句”的方法,可以在O(nk+1)算法时间复杂度获得SAT的满足解,而且成功地设计出3-SAT“子句消去法”求出满足解计算机程序,通过验证,证实了子句消去法理论的正确性与可靠性。

SAT问题是NP_complete问题中最基本的题目,其它的NP_complete问题基本都是在SAT问题的基础之上建立起来的。根据PNP问题公认的观点,只要有一个NP_complete问题有多项式时间算法,那么就可以断定P=NP。如今,我们找到了SAT问题的多项式时间复杂度的算法,因而可以说P=NP成立了。P=NP的后果如何?看看国外的PNP问题的专家们都是怎样认为的吧。

在英文维基百科的P versus NP problem中,关于P=NP的后果,有这样的阐述:

If P = NP, then theworld would be a profoundly different place than we usually assume it to be.There would be no special value in "creative leaps," no fundamentalgap between solving a problem and recognizing the solution once it's found.

ScottAaronson, MIT

如果P=NP,那么世界上必然有一个与我们平常认识不同的地方。创造性的飞跃没有了特殊的价值,在解决问题和首次找到问题解之间没有了差距。

                                                                      ——斯科特.阿若森  麻省理工学院  

A proof that P= NP could have stunning practical consequences, if the proof leads toefficient methods for solving some of the important problems in NP. Itis also possible that a proof would not lead directly to efficient methods,perhaps if the proof is non-constructive, or the size of thebounding polynomial is too big to be efficient in practice. The consequences,both positive and negative, arise since various NP-complete problems arefundamental in many fields.

如果一个证明导致NP领域许多重要的问题获得有效的解决方法,那么P=NP的证明后果是惊人的。这个证明可能不是直接提供的有效方法,也许这个证明是非建设性的,或者实际中多项式时间的边界太大,但是无论如何, NP完全问题证明的结果在许多领域中都是基础性的。

   还有,如果P=NP,那么基于计算复杂度的密码学是没有用处的。internet和电子商务都面临危险。


也许国外的专家们过于夸大了P=NP的重要性。但无论如何,我敢肯定,P=NP


2017-5-11


                                                       




https://wap.sciencenet.cn/blog-340399-1054324.html

上一篇:3-SAT满足解软件ZJXQF使用说明书
下一篇:活到老、学到老、研究到老
收藏 IP: 118.144.20.*| 热度|

1 icgwang

该博文允许注册用户评论 请点击登录 评论 (2 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-12-22 00:52

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部