计算机科学 ›› 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有重要和积极的意义。

关键词: HC问题, MSP问题, 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: HC problem, MSP 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] 高吉吉, 岳雪蓉, 陈智斌.
针对经典排序问题的一种新算法的近似比分析
Approximate Ratios Analysis of New Algorithm for Classical Parallel Scheduling
计算机科学, 2021, 48(4): 37-42. https://doi.org/10.11896/jsjkx.200600064
[2] 刘江, 周鸿昊.
一种布尔公式的代数逻辑约化新方法
New Algebraic Logic Reduction Method for Boolean Formula
计算机科学, 2020, 47(5): 32-37. https://doi.org/10.11896/jsjkx.190400018
[3] 吴添君 姜新文.
MSP问题NP完全性研究
On NP-completeness of MSP Problem
计算机科学, 2015, 42(7): 12-14. https://doi.org/10.11896/j.issn.1002-137X.2015.07.003
[4] 周 旭,李肯立,乐光学,朱开乐.
一种加群Z上离散对数问题的DNA计算算法
Fast Parallel Molecular Algorithm for Solving the Discrete Logarithm Problem over Group on Z DNA-based Computing
计算机科学, 2012, 39(4): 232-235.
[5] 樊硕,姜新文.
SAT问题可多项式归结到MSP问题
Proving NP-completeness of Polynomial Reduction from the SAT Problem to the MSP Problem
计算机科学, 2012, 39(11): 179-182.
[6] 张琨 王珩 刘凤玉.
一种时延约束的多点到多点组播路由启发式算法

计算机科学, 2005, 32(4): 107-109.
[7] 王元珍 裴小兵.
基于Skowron分明矩阵的快速约简算法

计算机科学, 2005, 32(4): 42-44.
[8] 张静 汤红波 李鸥 胡捍英.
单播和多播QoS路由问题研究及解决方法

计算机科学, 2005, 32(3): 36-38.
[9] 李燕 王秀峰.
DNA计算方法

计算机科学, 2004, 31(5): 142-143.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!