今天看到哈密顿回路图论有多项式算法了,求证一下论文靠谱程度,以及这个问题为什么可以说明 NP=P。

推荐  (0) | 6人关注关注
3个答案
4 0

方弦科学松鼠会成员,信息学硕士生

2013-06-04 05:26

别看了,这种东西基本上是浪费时间。如果真的想看证明的话,这里有很多,正着反着的都有:
http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
反正直觉告诉我这个不靠谱,我坚定认为最后肯定是用数理逻辑的方法做出来……或者是代数几何……这种纯算法在逻辑上的复杂度太低了……

3 0

首先这个论文基本是不靠谱的。这个东西要是证明出来了,绝对是科学界的爆炸大新闻。

然后我来解释下如果论文靠谱为啥能证明NP=P:

首先我们解释下什么叫“多项式时间算法”:如果一个问题有n个变量,如果求得这个问题的解需要的计算次数不超过n的k次方(这个就是程序员们常说的时间复杂度啦,k为常数),那么求解这个问题的算法就是一个“多项式时间算法”。

然后我们要知道“图灵机”这个玩意:
这个东西呢,是伟大的基友科学家计算机学科的奠基人图灵先生定义的一个基本的机器计算模型。
图灵机又分为两种,确定的图灵机和不确定的图灵机。
我们现在所用的电脑(地球上的所有的电脑)都是属于确定的图灵机。
不确定的图灵机是个理想理论模型,至今无人能实现。

再然后,解释下什么是NP和P:
一般说NP和P指的是两类问题。
其中P类问题指的是能够用确定的图灵机在多项式时间内找到解的问题,也就是有多项式时间算法的问题。比如排序问题。
NP类问题指的是能够用不确定的图灵机在多项式时间内找到解的问题,也就是如果不确定的图灵机存在的话,那么NP问题也是有多项式时间算法的。不过由于现实中不确定的图灵机并不存在,所以NP类的问题暂时都没有找到多项式时间算法。这一类问题的算法的时间复杂度一般都是 k的n次方,计算量会随着n的增大而急剧增大,一些规模不大的NP问题要用现在的计算机求出解估计等到太阳系毁灭都算不出来。。。

那么,有一个问题就是,NP类问题是不是一定没有多项式时间算法呢?

答案是,不知道!

因为没有人能证明NP类问题一定没有多项式时间算法。如果得到这个证明,那么就说明NP≠P。

在NP类问题里面还有一类问题叫NPC问题,也就是“NP完全”问题。
如果一个问题是NPC,那么所有的NP问题都可以规约为这个NPC问题,也就是所有的NP问题都可以用这个NPC问题来描述。所有的NPC问题都可以互相规约。

论文里提到哈密顿环问题就是一个NPC问题。
因为所有的NP问题都可以转化为哈密顿环问题,那么只要找到哈密顿环问题的多项式时间算法,那么所有的NP问题就都存在多项式时间算法了。
从而证明NP=P。

不过现在的学术观点一般倾向于NP≠P。
如果NP=P的话,那么现有的密码机制将全部失效,密码学的研究算是都白费的。

另外关于NP等不等于P这个问题,是7个千禧年大奖问题之一哦,证明出来了可以拿100万美元奖金的!

根据克雷数学研究所订定的规则,所有难题的解答必须发表在数学期刊上,并经过各方验证,只要通过两年验证期,每解破一题的解答者,会颁发奖金100万美元。

前几年的时候惠普实验室的一个研究员宣称证明了NP≠P,轰动了一下,不过没多久就被人发现了错误。。。

0 0

谁能告诉我这篇到底哪个地方不对?我觉得应该是在time complexity证明的地方

查看更多

添加回答

登录 后回答问题,你也可以用以下帐号直接登录

相关问答

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 家长监控 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2018] 6282-492号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区