七大世界數學難題之一P≠NP或被解
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位中國大陸同胞奉上獨立真實的關鍵資訊, 在危難時刻向他們發出預警,救他們於大瘟疫與其它社會危難之中。
看完這篇文章您覺得
- 日片《完美的日子》:光影交織中的美和釋然(組圖)
- 大開眼界!創記錄的「人體噴泉」(組圖)
- 習近平忌憚三個紅二代(組圖)
- 【宋紫鳳專欄】從潘美到潘仁美 是藝術加工還是神來之筆(組圖)
- 江曾一政策藏汙納垢 老虎前仆後繼終南捷徑(組圖)
- 中國經濟舊模式大潰敗 注定一個時代已經結束(圖)
- 黨內出大醜聞了,胡錦濤可不能無動於衷(組圖)
- 古狗解禁 中共內鬥浮上台面(組圖)
- 劉亞洲將軍預言政體轉型 外界評議
- 賈慶林外孫女考取美國名校 鄧小平孫子在華爾街
- 李嵐清之子李志群是這樣升遷的
- 貪官子女 二奶雲集加拿大
- 關係惡化? 胡錦濤下月恐不訪美了
- 誰在歪曲中共黨史?看習近平老爸的悲慘真相
- 中共肺炎(又称武漢肺炎)
- 病毒
- COVID-19
- 疫苗
- 台鐵
- 拜登
- 川普
- 特朗普
- 國安法
- 貿易戰
- 習近平
- 華為
- 三峽大壩
- 新疆棉
- 長江
- 洪水
- 袁弓夷
- 港版國安法
- 漢光演習
- 國民黨
- 退黨
- 弗洛伊德
- BLM
- 中共
- 閻麗夢
- 金正恩
- 王岐山
- 賴清德
- 孟晚舟
- 關稅
- 邊境牆
- 彭斯
- 美國
- 貿易談判
- 劉鶴
- 王滬寧
- 江澤民
- 崔永元
- 中南海
- 內幕
- 中共
- 反送中
- 貪官
- 情婦
- 腐敗
- 反腐
- 打虎
- 官場
- 看中國
- 一國兩制
- 法廣
- 社交媒體
- 往事微痕
- 出賣國土
- FB
- 六四
- 朝鮮
- 加拿大
- 脫歐
- 央行
- 債務
- 槓桿
- 美元
- 貨幣
- 人民幣
- 歐元
- 日元
- 港幣
- 房地產
- 樓市
- 財政
- 財富
- 中產
- 海參崴
- 台灣
- 蔡英文
- 北京
- 劉強東
- 大媽
- 房價
- 疫苗
- 非洲豬瘟
- 大陸
- P2P
- 霧霾
- 基因編輯
- 防火牆
- 維權
- 709律師
- 上訪
- 法輪功
- 網絡審查
- 活摘器官
- 江東六十四屯
- 唐努烏梁海
- 長白山
- 白龍尾島
- 江心坡
- SARS
- 新疆勞改營
- 言論自由
- 女主播
- 央視
- 華人
- 移民
- 華人
- 留學
- 海關
- 遣返
- 簽證
- 回國
- 入籍
- 綠卡
- 民生
- 海外
- 加拿大
- 澳洲
- 民國
- 桂軍
- 抗戰
- 孫中山
- 蔣介石
- 宋美齡
- 鄧小平
- 林彪
- 劉奇
- 中共
- 皇帝
- 諸葛亮
- 易經
- 幽默人生
- 智慧
- 感悟
- 手機
- 預言
- 奇聞
- UFO
- 外星人
- 壽命
- 文革
- 養生
- 紫鳳
- 貫明
- 李道真
- 軼飛
- 李雲飛
- 雲中君
- 辛思
- 夏聞
- 時代漫談
- 滄海
- 東方縱橫
- 唐柏橋
- 王尚一
- 江楓
- 黃清
- 李唐風
- 園丁
- 今濤拍暗
- 李青城
- 秦就石
- 中經研
- 秦天靖
- 江浩
- Eagle Vision
- 李子壬
- 馬新宇
- 馬來啟
- 紫君
- 秦山
- 陳破空
- 戴東尼
- 曹長青
- 邢仁濤
- 瑜正
- 簡易
- 肖川
- 伍凡
- 顧言
- 歸瑜
- 乙欣
- 陳泱潮
- 徐沛