Computer Science ›› 2020, Vol. 47 ›› Issue (7): 8-20.doi: 10.11896/jsjkx.191200176

• Computer Science Theory • Previous Articles     Next Articles

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)

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

CLC Number: 

  • 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] GAO Ji-ji, YUE Xue-rong, CHEN Zhi-bin. Approximate Ratios Analysis of New Algorithm for Classical Parallel Scheduling [J]. Computer Science, 2021, 48(4): 37-42.
[2] WU Tian-jun JIANG Xin-wen. On NP-completeness of MSP Problem [J]. Computer Science, 2015, 42(7): 12-14.
[3] . Proving NP-completeness of Polynomial Reduction from the SAT Problem to the MSP Problem [J]. Computer Science, 2012, 39(11): 179-182.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!