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

• 作者: 姜新文
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: MSP问题 HC问题 NP完全问题 多项式时间算法
• 年，卷（期）: 2020,（7）
• 所属期刊栏目: 计算机科学理论
• 页码范围: 8-20
• 页数: 13页
• 分类号: TP301.6
• 字数: 23892字
• 语种: 中文
• DOI: 10.11896/jsjkx.191200176

摘要

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有重要和积极的意义.