2020年7月出版的《計算機科學》(中國計算機學會會刊)發表了國防科技大學教授、湘潭大學計算機學院特聘教授姜新文題為《哈密頓圖判定問題的多項式時間算法》的論文,這標志著在數學和計算機科學領域中最為重要的難題之一"NP=P?"得到科學證明,論文刊出幾天后下載量近千次,引發有關學術群體熱議。

"NP=P?"也稱"NP≠P還是NP=P",實質是P對NP關系問題,被稱為世界級數學難題之一。

2000年5月,美國克雷數學研究所(CMI)在巴黎舉行的千年數學大會上宣布對攻克世界7個數學難題的懸賞。P對NP關系問題被列為新千年7大難題之首。2005年《科學》雜志將"NP=P?"問題作為數學科學的代表,列為25個學科難題之一。2018年《科學》雜志再次列出125個亟待解決的科學難題,其中第19個問題就包含"NP=P?"問題。

迄今為止,新千年7大數學難題中除了俄羅斯數學家佩雷爾曼2002年證明了有關拓撲學的"龐加萊猜想"之外,其他難題均懸而未決。

據介紹,20世紀,現代計算機問世,NP與P的關系問題就成為計算機科學和數學交叉領域的基礎科學問題。通常,算法求解一個問題需要耗費時間,這被稱為算法的時間復雜度。求解同一個問題的不同算法耗費的時間可能不同,只有采用多項式時間算法才能最有效解決問題。

NP≠P,其核心是否定不同選擇方法,認為有些問題不存在多項式算法。

而姜新文證明了"NP=P",表明多項式算法實際上是存在的。

姜新文從1986年開始講授《算法設計與分析》課程,結合此前學習圖論時關于哈密頓圖判定問題的思考,開始研究P對NP關系問題。9年之后,姜新文于1995年發表了研究成果《簡單無向圖H性質判定》,開始思考運用整體觀思路來處理一個有限系統的計算問題。

他首先建立了一套基于數學歸納法的證明框架,然后堅持探索滿足這套證明框架的算法設計。從1995年開始之后的15年中,經歷了2000次以上設計、修改與調整,到2010年底得到預期效果。姜新文35年的潛心探索,終于獲得成功!

"NP=P"得到證明具有重要的科學意義與應用價值。因為這將為計算機科學領域帶來截然不同的理論極限和發展前景。在現代經濟社會中,大量科研、生產、國防與社會服務過程都需要采用正確的快速計算方法。可以期待,在"NP=P時代",地球科學、生命科學、宇宙科學、環境科學、生物科技、材料工程、管理科學、數學科學、物理科學等多個學科的研究都將得到更深入的推進。

此外,由于現代密碼學是建立在NP≠P的假定之上,而現在NP=P得到證明,對密碼學的發展是一次巨大的科學挑戰。

相關論文信息:doi: 10.11896/jsjkx.191200176

總結

以上是生活随笔為你收集整理的Np计算机领域,我国数学家证明NP=P的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。