NP完全问题求解复杂性研究

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. Collecting 25 difficult problems that human being urgently want to solve, a list given by Science in 2005 contains the 'P vs. NP problem'. .Whether NP=P or not depends on the complexity to solve a NPC problem. Our research focuses on designing a polynomial algorithm for the well known Hamilton Circuit Problem. The final outcome of our proposal is hopeful to support NP=P..We have been working on this problem for more than 15 years. A amazingly simple algorithm has been designed and an endless process of verification has been launched since Oct., 2010. Until the end of Feb., 2012, for more than 45 millions of stochasticly generated graph, each of which has about 100 nodes, our algorithm always works out the same conclusion as a back tracking algorithm (the back tracking algorithm is designed to serve as Benchmark). No exception. Hence we write the proposal to continue our research on the valuable algorithm that we found,to simplify the complexity and the proof of the algorithm, and to apply our theory to solve other NP problem.

NP=?P的问题是计算机科学和数学中的著名问题。美国克雷数学研究院将其列为新千年7大急需解决的困难问题之首。Science杂志2005年将其列为人类亟待解决的25个困难问题之一。.NP完全问题的求解复杂性决定NP=P是否成立。哈密顿图判定问题是一个NP完全问题。哈密顿图判定问题本身也是图论中的难题。本项目重点研究哈密顿图判定问题求解的多项式时间算法。具有基础性的重大意义。.15年的持续研究使我们找到了求解求解哈密顿图判定问题一个新的算法。初步理论分析表明该算法为多项式算法。2010年10月至今超过4500万例100阶以上图的随机测试表明算法正确。国内外多次报告、研讨，以及国际权威杂志两轮审稿（完成一轮，二轮在审已8个月）至今未发现重要错误。需要进一步对我们提出的算法进行研究，需要进一步简化证明和降低复杂性以促进算法实用化，需要拓展应用我们的理论求解更多问题。

NP=?P 的问题是计算机科学和数学中的著名难题。美国克雷数学研究院将其列为新千年7大急需解决的困难问题之首。Science杂志2005年将其列为25个困难问题之19。.NP完全问题的求解复杂性决定NP=P是否成立。哈密顿图判定问题是一个NP完全问题。哈密顿图判定问题本身也是图论中的难题。本项目重点研究哈密顿图判定问题求解的多项式时间算法，研究结果暗含NP=P。具有基础性的重大意义。.本项目之前，我们的研究已经持续15年，本项目继续15年的努力。我们认为已经完成从想法到方法的完美跨越。设计的多项式时间算法已经投送国内外多家权威杂志，并在国内外多次报告、研讨。NP完全问题的多项式算法是本项目研究最重要的和最值得期待的输出，虽然还没有被权威杂志发表，但是科学鉴定的最后决战一定会打响。