content

七大世界數學難題之一P≠NP或被解

 2010-08-13 08:43 桌面版 简体 打賞 0
    小字

P≠NP,一個簡潔的論文標題,或許預示著七大世界數學難題之一的P問題(多項式演算法)對NP問題(非多項式演算法)終於有了答案。據英國《新科學家》雜誌網站8月11日(北京時間)報導,美國惠普實驗室的數學家維奈·迪奧拉里卡已經於6日提交了關於論證該問題的論文草稿,如果此答案被證實無誤,那麼他將獲得由美國克雷數學研究所提供的 100萬美元獎金。

P對NP問題是克雷數學研究所高額懸賞的七個千禧年難題之一,同時也是計算機科學領域的最大難題,關係到計算機完成一項任務的速度到底有多快。有些問題計算起來很容易,利用多項式演算法很快能解決,比如求若干個數的乘積,這類問題被稱作P問題;另一類問題計算過程比較繁瑣,但驗證答案卻很容易,比如把整數44427進行因數分解,求解過程可能會很費時,但如果告訴你答案是177×251,簡單計算即可驗證答案是對的,這類問題就被歸為NP問題。

因此,如果P=NP,那麼每個答案很容易得到驗證的問題也同樣可以輕鬆求解。這將對計算機安全構成巨大威脅,目前加密系統的破解就相當於要將一個整數分解為幾個因數的乘積,正是其求解過程的繁瑣,才能杜絕黑客的入侵。

而現在,迪奧拉里卡圍繞一個眾所周知的NP問題進行論證,給出了P≠NP的答案。這就是布爾可滿足性問題(Boolean Satisfiability Problem),即詢問一組邏輯陳述是否能同時成立或者互相矛盾。迪奧拉里卡聲稱,他已經證明,任何程序都無法迅速解答這個問題,因此,它不是一個P問題。

如果迪奧拉里卡的答案成立,說明P問題和NP問題是不同的兩類問題,這也意味著計算機處理問題的能力有限,很多任務的複雜性從根本上來說也許是無法簡化的。

對於有些NP問題,包括因數分解,P≠NP的結果並沒有明確表示它們是不能被快速解答的;但對於其子集NP完全問題,卻注定了其無法很快得到解決。其中一個著名的例子就是旅行商問題 (Travelling Salesman Problem),即尋找從一個城市到另一個城市的最短路線,答案非常容易驗證,不過,如果P≠NP,就沒有計算機程序可以迅速給出這個答案。

迪奧拉里卡的論文草稿已經得到了複雜性理論家的認可,但一週後公布的論文終稿還將接受嚴格的審查。

来源:網易探索 --版權所有,任何形式轉載需看中國授權許可。 嚴禁建立鏡像網站。
本文短網址:


【誠徵榮譽會員】溪流能夠匯成大海,小善可以成就大愛。我們向全球華人誠意徵集萬名榮譽會員:每位榮譽會員每年只需支付一份訂閱費用,成為《看中國》網站的榮譽會員,就可以助力我們突破審查與封鎖,向至少10000位中國大陸同胞奉上獨立真實的關鍵資訊, 在危難時刻向他們發出預警,救他們於大瘟疫與其它社會危難之中。

分享到:

看完那這篇文章覺得

評論

暢所欲言,各抒己見,理性交流,拒絕謾罵。

留言分頁:
分頁:


x
我們和我們的合作夥伴在我們的網站上使用Cookie等技術來個性化內容和廣告並分析我們的流量。點擊下方同意在網路上使用此技術。您要使用我們網站服務就需要接受此條款。 詳細隱私條款. 同意