《NP完全問題求解複雜性研究》是依託中國人民解放軍國防科技大學，由姜新文擔任項目負責人的面上項目。
基本介紹
- 中文名：NP完全問題求解複雜性研究
- 項目類別：面上項目
- 項目負責人：姜新文
- 依託單位：中國人民解放軍國防科技大學
中文摘要,結題摘要,
中文摘要
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完全問題的多項式算法是本項目研究最重要的和最值得期待的輸出，雖然還沒有被權威雜誌發表，但是科學鑑定的最後決戰一定會打響。
