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

项目名称： NP完全问题求解复杂性研究

项目编号： No.61272010

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 自动化技术、计算机技术

项目作者： 姜新文

作者单位： 中国人民解放军国防科学技术大学

项目金额： 60万元

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

中文关键词： NP完全问题；多项式算法；计算复杂性；哈密顿图问题；MSP问题

英文摘要： 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.

英文关键词： NPC Problem；Polynomial Algorithm；Complexity；HC Problem；MSP Problem