當(dāng)前位置：首頁 > 消費(fèi)電子 > 消費(fèi)電子

惠普實(shí)驗(yàn)室數(shù)學(xué)家破解計算機(jī)科學(xué)最大難題

時間：2010-08-12 11:46:34

關(guān)鍵字：惠普計算機(jī) 因數(shù) PROBLEM

手機(jī)看文章

掃描二維碼
隨時隨地手機(jī)看文章

[導(dǎo)讀]P≠NP，一個簡潔的論文標(biāo)題，或許預(yù)示著七大世界數(shù)學(xué)難題之一的P問題（多項(xiàng)式算法）對NP問題（非多項(xiàng)式算法）終于有了答案。據(jù)英國《新科學(xué)家》雜志網(wǎng)站8月11日（北京時間）報道，美國惠普實(shí)驗(yàn)室的數(shù)學(xué)家維奈&#18

P≠NP，一個簡潔的論文標(biāo)題，或許預(yù)示著七大世界數(shù)學(xué)難題之一的P問題（多項(xiàng)式算法）對NP問題（非多項(xiàng)式算法）終于有了答案。據(jù)英國《新科學(xué)家》雜志網(wǎng)站8月11日（北京時間）報道，美國惠普實(shí)驗(yàn)室的數(shù)學(xué)家維奈·迪奧拉里卡已經(jīng)于6日提交了關(guān)于論證該問題的論文草稿，如果此答案被證實(shí)無誤，那么他將獲得由美國克雷數(shù)學(xué)研究所提供的100萬美元獎金。
P對NP問題是克雷數(shù)學(xué)研究所高額懸賞的七個千禧年難題之一，同時也是計算機(jī)科學(xué)領(lǐng)域的最大難題，關(guān)系到計算機(jī)完成一項(xiàng)任務(wù)的速度到底有多快。有些問題計算起來很容易，利用多項(xiàng)式算法很快能解決，比如求若干個數(shù)的乘積，這類問題被稱作P問題；另一類問題計算過程比較繁瑣，但驗(yàn)證答案卻很容易，比如把整數(shù)44427進(jìn)行因數(shù)分解，求解過程可能會很費(fèi)時，但如果告訴你答案是177×251，簡單計算即可驗(yàn)證答案是對的，這類問題就被歸為NP問題。
因此，如果P=NP，那么每個答案很容易得到驗(yàn)證的問題也同樣可以輕松求解。這將對計算機(jī)安全構(gòu)成巨大威脅，目前加密系統(tǒng)的破解就相當(dāng)于要將一個整數(shù)分解為幾個因數(shù)的乘積，正是其求解過程的繁瑣，才能杜絕黑客的入侵。
而現(xiàn)在，迪奧拉里卡圍繞一個眾所周知的NP問題進(jìn)行論證，給出了P≠NP的答案。這就是布爾可滿足性問題(Boolean Satisfiability Problem)，即詢問一組邏輯陳述是否能同時成立或者互相矛盾。迪奧拉里卡聲稱，他已經(jīng)證明，任何程序都無法迅速解答這個問題，因此，它不是一個P問題。
如果迪奧拉里卡的答案成立，說明P問題和NP問題是不同的兩類問題，這也意味著計算機(jī)處理問題的能力有限，很多任務(wù)的復(fù)雜性從根本上來說也許是無法簡化的。
對于有些NP問題，包括因數(shù)分解，P≠NP的結(jié)果并沒有明確表示它們是不能被快速解答的；但對于其子集NP完全問題，卻注定了其無法很快得到解決。其中一個著名的例子就是旅行商問題(Travelling Salesman Problem)，即尋找從一個城市到另一個城市的最短路線，答案非常容易驗(yàn)證，不過，如果P≠NP，就沒有計算機(jī)程序可以迅速給出這個答案。
迪奧拉里卡的論文草稿已經(jīng)得到了復(fù)雜性理論家的認(rèn)可，但一周后公布的論文終稿還將接受嚴(yán)格的審查。(記者陳丹)

本站聲明：本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布，目的在于傳遞更多信息，并不代表本站贊同其觀點(diǎn)，本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者，如若文章內(nèi)容侵犯您的權(quán)益，請及時聯(lián)系本站刪除。

換一批

國外是怎么學(xué)習(xí)計算機(jī)的？

微信的好友列表里就有在德國、英國、日本、美國等國家留學(xué)的同學(xué)，每次遇到這些網(wǎng)友，我都喜歡問一個問題：你們那里是怎么教計算機(jī)的？在跟他們的聊天對話中，我了解到了不同國家在計算機(jī)教育方面的差異。

關(guān)鍵字：微信同學(xué) 計算機(jī)

[消費(fèi)電子]

算力“吊打”全球的“雷神”，英偉達(dá)能否借助元宇宙走出“至暗時刻”？

英偉達(dá)9月20日的“春晚”GTC沒能力挽狂瀾。美東時間9月26日，英偉達(dá)收盤于122.28美元。一個月前的8月26日，英偉達(dá)開啟了本輪下行，從當(dāng)天開盤的178.57美元一路下探，至今已跌去超三成。

關(guān)鍵字：算力英偉達(dá) 計算機(jī)

[消費(fèi)電子]

中國超級計算機(jī)將成全國技術(shù)創(chuàng)新和產(chǎn)業(yè)發(fā)展的“超級馬達(dá)”

中國超級計算機(jī)是如何實(shí)現(xiàn)從無到有，從大型機(jī)到巨型機(jī)進(jìn)化的?1950年3月，中央人民廣播電臺播發(fā)了一封書信，信中說“梁園雖好，非久居之鄉(xiāng)，歸去來兮。

關(guān)鍵字：超級計算機(jī) 進(jìn)化史

[嵌入式新聞]

互聯(lián)網(wǎng)已經(jīng)進(jìn)入了“物聯(lián)網(wǎng)”時代

隨著IT技術(shù)飛速發(fā)展，互聯(lián)網(wǎng)已經(jīng)進(jìn)入了“物聯(lián)網(wǎng)”時代。物聯(lián)網(wǎng)中需要的大量設(shè)備不在依賴人與人之間的交互產(chǎn)生聯(lián)系，更多通過協(xié)議、通信、程序設(shè)計等方式連接到一處。即 “物聯(lián)網(wǎng)”的目的則是讓所有的物品都具有計算機(jī)的智能但并不以通...

關(guān)鍵字：嵌入式物聯(lián)網(wǎng) 計算機(jī)

[嵌入式藝術(shù)]

一文帶你了解音頻的那些事！

現(xiàn)實(shí)生活中，我們聽到的聲音都是時間連續(xù)的，我們稱為這種信號叫模擬信號。模擬信號需要進(jìn)行數(shù)字化以后才能在計算機(jī)中使用。

關(guān)鍵字：模擬信號數(shù)字化計算機(jī)

[嵌入式新聞]

萬物智聯(lián)時代嵌入式技術(shù)及其應(yīng)用的形態(tài)將更加豐富和多元

萬物智聯(lián)時代，嵌入式技術(shù)及其應(yīng)用的形態(tài)將更加豐富和多元，同時也將日益呈現(xiàn)深度物理融合、混合架構(gòu)共存、群體智能協(xié)同、網(wǎng)絡(luò)安全攸關(guān)等諸多新的計算特性。顯然，經(jīng)典的嵌入式系統(tǒng)體系結(jié)構(gòu)、軟硬件技術(shù)和開發(fā)方法都已很難應(yīng)對新趨勢下的...

關(guān)鍵字：嵌入式物聯(lián)網(wǎng) 計算機(jī)

[嵌入式新聞]

嵌入式也必將成為物聯(lián)網(wǎng)發(fā)展的先驅(qū)

物聯(lián)網(wǎng)是新一代信息技術(shù)的重要組成部分，是互聯(lián)網(wǎng)與嵌入式系統(tǒng)發(fā)展到高級階段的融合。通用計算機(jī)經(jīng)歷了從智慧平臺到互聯(lián)網(wǎng)的獨(dú)立發(fā)展道路;嵌入式系統(tǒng)則經(jīng)歷了智慧物聯(lián)到局域智慧物聯(lián)的獨(dú)立發(fā)展道路。

關(guān)鍵字：嵌入式物聯(lián)網(wǎng) 計算機(jī)

[快科技]