计算机科学 ›› 2020, Vol. 47 ›› Issue (7): 8-20.doi: 10.11896/jsjkx.191200176

• 计算机科学理论 • 上一篇    下一篇

哈密顿图判定问题的多项式时间算法

姜新文   

  1. 湘潭大学计算机学院·网络空间安全学院 湖南 湘潭411105
    国防科技大学计算机学院 长沙410073
    智能计算和信息处理教育部重点实验室 湖南 湘潭411105
  • 收稿日期:2019-12-30 出版日期:2020-07-15 发布日期:2020-07-16
  • 通讯作者: 姜新文(xinwenjiang@sina.com)
  • 基金资助:
    国家自然科学基金 (61272010)

Polynomial Time Algorithm for Hamilton Circuit Problem

JIANG Xin-wen   

  1. School of Computer Science & School of Cyberspace Science,Xiangtan University,Xiangtan,Hunan 411105,China
    School of Computer,National University of Defense Technology,Changsha 410073,China
    The MOE Laboratory of Intelligent Computing & Information Processing,Xiangtan,Hunan 410005,China
  • Received:2019-12-30 Online:2020-07-15 Published:2020-07-16
  • About author:JIANG Xin-wen,born in 1962,professor,is a member of China Computer Federation and a member of China Society for Industrial and Applied Mathematics (CSIAM),serving for their blockchain committee bothly.His main research interests include algorithm and computational complexity,information security and blockchain technology.He is a teacher who received several science and technology progress awards,including one national-level prize and six ministerial-level prizes.He was earned Army Yucai Award twice due to his distinguished contribution in talents cultivation.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61272010)

摘要: NP=?P(即NP是否等于P)的问题是计算机科学和数学中的重要问题。美国克雷数学研究院将其列为新千年七大困难问题之首,2005年Science将其列为25个困难问题之19。Science最近列出的125个亟待解决的重要问题中,第19个问题实质上就是NP=?P的问题。如果NP=P,对于很多困扰科学研究的困难计算问题,理论上就存在多项式时间算法来迅速求解它们。而现代密码学建立在NP≠P的假设之上。人们希望存在难解问题,希望基于难解问题构造加密算法,希望能够利用难解问题的求解复杂性对抗分析和攻击。如果NP=P,所有在NP≠P假定之上开展的计算研究都至少需要重新审视其意义。NP完全问题的求解复杂性决定NP=P是否成立。针对一个被称为MSP问题的新问题,文中提出了一个关于MSP问题的多项式时间算法,并给出了该算法的证明和时间复杂性分析。由于已经发表了十多个经典的NP完全问题到MSP问题的归结以及MSP问题到SAT问题的归结,因此MSP问题存在多项式时间算法这样一个研究结果对于研究NP=P有重要和积极的意义。

关键词: MSP问题, HC问题, NP完全问题, 多项式时间算法

Abstract: The ‘P vs.NP problem’ is the most famous and difficult problem in math.and computer science.Among the seven most important and difficult problems that the American Clay Mathematics Institute declared in 2000,this problem ranks the first one.Collecting 25 difficult problems that human being urgently want to solve,a list given by Science in 2005 contains the ‘P vs.NP problem’,ranking 19th.In the latest list of the most important 125 questions given by Science,the ‘P vs.NP problem’ ranks 19th too.Modern cryptography is based on the assumption that NP≠P.Whether NP=P or not depends on the complexity to solve a NPC problem.A new NP problem which is called MSP is proposed and a polynomial time algorithm to solve MSP is designed in this paper.To prove that the MSP problem is a NP complete problem,several papers,that reduced more than 10 NP complete problems to the MSP problem and reversely reduced the MSP problem to the SAT problem,were published in the last several years.Hence the result maybe helpful for proving NP=P.

Key words: MSP problem, HC problem, NP-comlete problem, Polynomial time algorithm

中图分类号: 

  • TP301.6
[1] THE CLAY MATHEMATICS INSTITUTE.P vs.NP Problem [EB/OL].https://www.claymath.org/millennium-problems/p-vs-np-problem.
[2] SCIENCE (AAAS).125 Questions of Science [EB/OL].http://www.sciencemag.org/site/feature/misc/webfeat/125th/.
[3] FORTNOW L.The status of the P versus NP problem[J].Communications of the ACM,2009,52(9):78-86.
[4] COOK S.The importance of the P versus NP question[J].Journal of the ACM (JACM),2003,50(1):27-29.
[5] THE CLAY MATHEMATICS INSTITUTE.Millennium Problems [EB/OL].https://www.claymath.org/millennium-problems/.
[6] KAYAL N.The complexity of the annihilating polynomial[C]//2009 24th Annual IEEE Conference on Computational Comple-xity.IEEE,2009:184-193.
[7] DEOLALIKAR V.P≠NP [EB/OL].https://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf.
[8] VARDI M Y.on P,nP,and computational complexity[J].Communications of the ACM,2010,53(11):5.
[9] AGRAWAL M,KAYAL N,SAXENA N.PRIMES is in P[J].Annals of mathematics,2004,160(2):781-793.
[10] VALIANT L G.Quantum circuits that can be simulated classically in polynomial time[J].SIAM Journal on Computing,2002,31(4):1229-1254.
[11] KNUTH D.All questions answered[J].Notices of the AMS,2002,49(3):318-324.
[12] GASARCH W I.The p=?np poll[J].Sigact News,2002,33(2):34-47.
[13] GAREY M R,JOHNSON D S.Computers and intractability:A guide to the theory of NP-completeness [M].San Francisco:freeman,1979.
[14] JIANG X W.Determining the H Property of A Graph by Changing It into Multistage Graph[J].Computing Technology and Automation,2004 23(2):52-54.
[15] JIANG X W,Wang Q,JIANG Z H.The fourth version of the Proof for ZH Algorithm to Solve MSP Problem[J].Computing Technology and Automation,2010,29(3):35-48.
[16] JIANG X W,PENG L H,WANG Q.MSP Problem:Its NP-Completeness and its Algorithm[C]//2010 Proceedings of the 5th International Conference on Ubiquitous Information Technologies and Applications.IEEE,2010:1-5.
[17] JIANG X W.A Polynomial Time Algorithm for the Hamilton Circuit Problem[J].arXiv preprint arXiv:1305.5976,2013.
[18] JIANG X W,LIU W W,WU T J,et al.Reductions from MSP to SAT and from SUBSET SUM to MSP[J].Journal of Computational Information Systems,2014,10(3):1287-1295.
[19] FAN S,JIANG X W,PENG L H.Polynomial-time heuristic algorithms for several NP-complete optimization problems[J].Journal of Computational Information Systems,2014,10(22):9707-9721.
[20] JIANG X W,WU T J,LI P K,et al.A New Algorithm for the MSP Problem[J].Computing Technology and Automation,2016,35(1):60-70.
[1] 刘江, 周鸿昊. 一种布尔公式的代数逻辑约化新方法[J]. 计算机科学, 2020, 47(5): 32-37.
[2] 吴添君 姜新文. MSP问题NP完全性研究[J]. 计算机科学, 2015, 42(7): 12-14.
[3] 周 旭,李肯立,乐光学,朱开乐. 一种加群Z上离散对数问题的DNA计算算法[J]. 计算机科学, 2012, 39(4): 232-235.
[4] 樊硕,姜新文. SAT问题可多项式归结到MSP问题[J]. 计算机科学, 2012, 39(11): 179-182.
[5] 张琨 王珩 刘凤玉. 一种时延约束的多点到多点组播路由启发式算法[J]. 计算机科学, 2005, 32(4): 107-109.
[6] 王元珍 裴小兵. 基于Skowron分明矩阵的快速约简算法[J]. 计算机科学, 2005, 32(4): 42-44.
[7] 张静 汤红波 李鸥 胡捍英. 单播和多播QoS路由问题研究及解决方法[J]. 计算机科学, 2005, 32(3): 36-38.
[8] 李燕 王秀峰. DNA计算方法[J]. 计算机科学, 2004, 31(5): 142-143.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .