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

姜新文

首页> 中文期刊> 《计算机科学》 >哈密顿图判定问题的多项式时间算法

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

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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

著录项

来源
《计算机科学》 |2020年第7期|8-20|共13页
作者
姜新文;
展开▼
作者单位

湘潭大学计算机学院·网络空间安全学院湖南湘潭411105;

国防科技大学计算机学院长沙410073;

智能计算和信息处理教育部重点实验室湖南湘潭411105;

展开▼
原文格式 PDF
正文语种 chi
中图分类算法理论;
关键词
MSP问题; HC问题; NP完全问题; 多项式时间算法;

相似文献

中文文献
外文文献
专利

1. 求解哈密顿图判定问题的一个新算法 [J] . 姜新文 . 计算技术与自动化 . 1997,第001期
2. 一个BCNF的多项式时间判定算法 [J] . 刘国华 ,郝忠孝 . 计算机研究与发展 . 1998,第004期
3. 论欧拉图、哈密顿图的判定及应用 [J] . 伍庆成 . 中国高新技术企业 . 2007,第007期
4. 一个O(n3)多项式时间算法解决有向图次短路问题 [J] . 曾庆红 ,杨桥艳 . 保山学院学报 . 2020,第005期
5. 线性比式和优化问题的完全多项式时间近似算法 [J] . 申子慧 ,申培萍 . 应用数学 . 2019,第1期
6. SAT问题多项式时间算法-一个稳定的NP问题算法 [C] . 崔刚 . 中科院自动化研究所自动化与信息技术发展战略研讨会暨2003年学术年会 . 2003
7. 两类分式规划问题的全局多项式时间近似算法 [A] . 赵小科 . 2013

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

摘要

著录项

相似文献

相关主题

期刊订阅