求解哈密顿图判定问题的一个新算法

本文给出来解哈密顿图判定问题（即HC问题）的一个算法及其证明．

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

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

Z-H算法正确性证明第四次改写

提出多级图简单路径求解问题,我们称之为MSP问题。给出求解该问题的Z-H算法,证明算法的正确性,分析算法的时间复杂性。最后通过将HC问题(哈密顿图判定问题)多项式归结成MSP问题,证明MSP问题的NP完全性质。本文极大地简化文献[6,7]中αβ引理的证明,特别是对证明过程中的各种情形进行分割,将一个巨大的证明分成系列引理。

简单无向图H性判定Determining the H Property of A Simple Undirected G

本文给出求解ＨＣ问题的一个多项式算法及其证明，实际运行也表明了算法的正确性。

用转换成多级图的方法判定图的H性质

给出了哈密顿图判定问题的一个算法。思想是先将简单无向图转换成多级图,然后证明简单无向图中哈密顿回路存在性与多级图中简单路径(定义见正文)存在性的等价性,最后通过多级图中简单路径存在性的判定实现简单无向图H性质判定。