wangjinliang10的个人博客分享 http://blog.sciencenet.cn/u/wangjinliang10

博文

世界数学难题之“P对NP问题”有望被破解

已有 583 次阅读 2019-7-14 12:40 |个人分类:P对NP问题|系统分类:论文交流| salesman, P对NP问题, 旅行推销商问题, salesman, salesman, salesman, salesman, salesman, salesman, salesman

        我们于2018年12月公开了一项研究成果,该成果有望解决“P对NP问题”。之所以未接受媒体报道和迟迟未发博文是出于慎重考虑。

  P对NP问题Clay数学研究所于2000年发起并悬赏100万美元想解决的七大世界数学难题之一。在这七个问题之中目前只有“庞加莱猜想”已被解决,是2003年被俄罗斯数学家Grigoriy Perelman解决的。“黎曼猜想”曾因英国数学家Michael Francis Atiyah爵士于2018年9月24日的演讲而轰动全球,但遗憾的是其证明缺少说服力。按照评奖规则每个证明过程都需要以正式论文的形式发表并经受业内专家长达两年的检验。当然,我们的论文也需要经历这样的过程。希望Clay研究所能够注意到这份研究报告并将其纳入候选名单,因为我们所选择的杂志在其征题范围内。之所以选择开放期刊而不是传统期刊主要是出于出版高效且阅读便捷的考量。不过,由于杂志层次较低,尚未引起学者的普遍关注。

       “P对NP问题是计算复杂性领域中的核心问题P类是确定性问题的集合,其中的每个问题都可以用某个含有有限步运算的算法来解决,这些步骤的总计算量不超过输入量n的有限次多项式。NP类代表在非确定性的多项式时间内能够解决的问题的集合,一般其总计算步骤是输入量n的指数形式,所耗费的计算时间往往是惊人的。P类问题隶属NP问题。而NP-完全问题是一类具有典型代表性的问题,只要能为其中的某一个问题找到一个快速算法就意味着所有的NP问题都有快速算法,从而意味着P类和NP类是一样的。

       著名的旅行商问题是一个非常典型的NP-完全问题。问题如下:一个推销商从某地出发去n个城市推销商品,问跑遍每个城市并回到原地的最短路径如何计算?一般而言,其计算复杂度非常高,涉及n的阶乘个步骤。我们发展了一种全新的最值删除法,其快速算法仅涉及n4次方个步骤。“P=NP”这一结论是作为推论给出的。这是一个令人惊奇的结果,因为绝大多数人曾相信PNP是不同的。

        感兴趣者请查阅下述论文:

Wang, J. L. (2018). Fast Algorithm for the Travelling Salesman Problem and the Proof of P =NP. 

 Applied Mathematics, 9, 1351-1359. doi: 10.4236/am.2018.912088. 

【论文链接】 https://www.scirp.org/journal/PaperInformation.aspx?PaperID=89255 



http://blog.sciencenet.cn/blog-686810-1189454.html

上一篇:请大家看看这些是不是远古生物化石?

1 刘钢

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

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-8-24 06:50

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部