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

发布时间：2022-10-29 11:34

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

【文章页数】：13 页

【文章目录】：
1 问题的引入及若干定义
2 求解MSP问题的ZH算法
    2.1 4个基本算子的定义
    2.2 ZH算法的复杂性分析和必要性证明
    2.3 充分性证明准备
        2.3.1 两个函数的定义
        2.3.2 构造证明框架
    2.4 αβ定理及其证明
    2.5 ZH算法的充分性证明
3 MSP∈NPC的证明以及本文结论


【参考文献】：
期刊论文
[1]MSP问题的一个求解算法[J]. 姜新文,吴添君,李鹏坤,樊硕,周泰杨,魏登萍.  计算技术与自动化. 2016(01)
[2]Z-H算法正确性证明第四次改写[J]. 姜新文,王琪,姜子恒.  计算技术与自动化. 2010(03)
[3]用转换成多级图的方法判定图的H性质[J]. 姜新文.  计算技术与自动化. 2004(02)



本文编号：3697614