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

博文

我们攻克了计算机理论领域最难题?NP=P! 精选

已有 11836 次阅读 2016-6-2 22:50 |系统分类:科研笔记|关键词:学者| 问题


 任何一个计算机专业的研究人员,都可能了解 P vs NP问题;甚至有部分早就开始着手尝试攻克这一难题。该问题是2000 Clay Mathematics InstituteCMI公布的7个世纪难题之一(目前有1个已被攻破)。攻克其中任何一个可获得百万美金大奖;同时肯定还有其它大奖等着拿。这不仅是获奖的问题,一定会成为计算机和数学等相关学科理论研究的一个里程碑式突破。

  Gerhard Woeginger教授维护的非官方 P vs NP 网页数据显示,从1986到2016年5月,有全世界约116篇论文尝试解决该问题(其中中国学者在这个网站上的论文约10篇),这些论文的结果至今仍然未得到包括CMI等国际权威机构和专家的公认,尽管有少数已经在国际期刊或会议上发表。 其中53% (62篇)认为答案是NP=P; 42% (49篇)认为答案是NP!=P;另外5%(5篇)认为该问题不可确定(Undecidable), 或不可证明(Unprovable),或不可知(Unknown)。这些论文中有9篇是与TSP(Traveling Salesman Problem)问题相关的论文。

本人也是从TSP问题出发尝试解决这一问题,但是我不是尝试TSP问题的准确解,而是提出一个全新思路:对2006年UC Berkeley学者发表的Papadimitriou-Vempala定理(Christos H.Papadimitriou and Santosh Vempala, On the approximability of the travelingsalesman problem,Combinatorica 26 (1) (2006) 101-120.)进行NP=P的证明。该定理认为,除非NP=P, 对于TSP问题在理论上无法找到一个多项式时间内近似比低于(220/219)的算法。


  我开始尝试该问题,大概是在2009年左右利用部分业余时间。首先我需要找到一个质量更高(近似比低于1.0045)的近似算法。 很遗憾,从1976年哈佛学者N. Christofides建立了近似比为1.5的Christofides算法以来,全世界学者对于欧式空间满足三角形关系的TSP问题(有称为Metric TSP)尚无更好的近似比算法。在Christofides算法基础上并结合K.Helsgaun 教授的LKH算法(K. Helsgaun,Generalk-opt submoves for the Lin-Kernighan TSP heuristic. Mathematical ProgrammingComputation, 2009,doi: 10.1007/s12532-009-0004-6.)等业界已有结果,经过反复证明和验证,我们使用Truncated Generalized Beta Distribution(TGB)模型,能获得近似比更好的算法,在我们的论文(Wenhong Tian,Chaojie Huang, Xinyang Wang, Qin Xiong, ObtainingQuality-Proved Near Optimal Results for Traveling Salesman Problems, https://arxiv.org/abs/1502.00447,submitted Feb 2nd 2015,已经录用,待正式发表)中,我们给出了我们的理论证明和使用TSPLIB实例计算的结果。 我们称该论文算法为TGB算法。


  2016年3月,我们又近一步,在TGB算法基础上提出Iterative Truncated Generalized Beta distribution Based on Christofides Algorithm (ITGBC)算法,针对2006年Papadimitriou-Vempala定理,我们首先从理论上证明通过ITGBC算法获得近似比低于1.0045的迭代条件;然后使用例子,包括所有对称型TSPLIB 例子和目前能够获得的巨无霸Metric TSP 问题(目前最大的World TSP问题,共有1,904,711个节点),甚至包括非对称(ATSP) TSBLIB例子,验证ITGBC算法都能在多项式时间内获得近似比低于1.0045的结果,从而提出了满足Papadimitriou-Vempala定理中NP=P的条件,因此证明NP=P.  该论文目前在https://arxiv.org/abs/1605.06183(2016年5月20日),同时在杂志评审中,欢迎同行指正,并提完善建议。

    非常感谢!




https://m.sciencenet.cn/blog-1028294-982065.html

上一篇:推荐《数据中心资源优化调度:理论与实践》一书
下一篇:华为的迷航与教师身价的上涨

14 刘钢 杨轶杰 徐明昆 黄永义 李颖业 刘锋 姜咏江 强涛 xlianggg shenlu grdegr yunpeng3 dulizhi95 zjzhaokeqin

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

数据加载中...

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

GMT+8, 2022-9-28 07:50

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部