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

Polynomial Time Algorithm for Hamilton Circuit Problem

作　　者：姜新文 JIANG Xin-wen(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)

机构地区：[1]湘潭大学计算机学院·网络空间安全学院,湖南湘潭411105 [2]国防科技大学计算机学院,长沙410073 [3]智能计算和信息处理教育部重点实验室,湖南湘潭411105

出　　处：《计算机科学》2020年第7期8-20,共13页Computer Science

基　　金：国家自然科学基金(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有重要和积极的意义。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.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]