 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 9 | 1/1 | 返回列表 |
| 查看: 2094 | 回復: 8 | |||
[交流]
【分享】惠普研究員稱已解決計算機科學第一難題 已有8人參與
|
|
轉(zhuǎn)自：http://news.cnblogs.com/n/70425/ 這幾天惠普新聞不斷。其實技術(shù)人員更應該關(guān)心的，不是那個CEO的緋聞女郎是否漂亮，CEO是否因公司政治蒙冤下臺，而是另一件可能會名垂青史的大事：一位名為Vinay Deolalikar的70后印度籍惠普研究員8月6日在自己的網(wǎng)站發(fā)布了一篇名為“P is not equal to NP”的論文（點擊下載），也就是說，他認為自己證明了P不等于NP！ 學過計算機科學理論的人都應該知道，計算機科學中有一個天字第一號問題一直沒有解決，引得無數(shù)圖靈獎得主和頂級計算機科學家競折腰，這個圣杯就是P/NP問題。事實上，這個問題也位列Clay數(shù)學研究所重金征解的七大數(shù)學難題之首，與我們凡夫俗子也多少知道的黎曼假設(shè)和龐加萊猜想并列。解決其中任何一道難題，都可以得到100萬美元獎金。其中，龐加萊猜想已被我們時代最偉大的Geek格里戈里•佩雷爾曼于2002年解決。 簡單的說，P問題是指能找到迅速（準確地說是多項式時間內(nèi)）解決算法的問題，P是Polynomial（多項式）時間的第一個字母。而NP問題，是指這個問題的解能夠迅速（準確地說是在多項式的時間里）猜測并驗證，但是很難找到，NP是Nondeterministic Polynomial （非確定多項式）的首字母縮寫。所以，P=NP？問題實際上是要證明或者推翻，P問題和NP問題不等價。由于NPC（NP-Complete）問題的存在，學術(shù)界普遍認為P不等于NP，但始終無法給出令人滿意的證明。 現(xiàn)在，Vinay Deolalikar宣布自己摘取了這項桂冠。他已經(jīng)將論文發(fā)給多位各個領(lǐng)域的頂尖專家進行同行評審。目前尚沒有得到任何正式的確認。不過，這個問題的提出者、圖靈獎得主Stephen Cook評論，（Deolalikar的）“聲明看上去比較嚴肅”。 著名的計算理論博客、佐治亞理工學院計算機科學教授Dick Lipton也發(fā)表文章簡單解釋了論文的思路，認為這項工作是嚴肅的。Lipton在文中說，Deolalikar是通過有限模型理論搭橋，引出反證，用到了Moshe Vardi (1982)和Neil Immerman (1986)的結(jié)論。 8月9日，Lipton又綜合已有的對論文的評論，發(fā)表了新的文章，認為證明肯定存在錯誤，但他又表示，這是任何突破性研究都無法避免的。該證明的策略是否證明，存在的問題是否能夠修正，仍然有待研究。 此外，猶他大學計算機學院的助理教授Suresh Venkatasubramanian通過Google Docs（鏈接,可能無法訪問）來討論這一證明，充分利用集體智慧，你也可以加入！文檔本身應該是LaTeX格式的。 袁泳在Twitter上分析了Deolalikar的思路，“是通過編碼K-SAT構(gòu)造某種有序結(jié)構(gòu)。如果NP=P，那根據(jù)Vardi的定理，K-SAT能用FO(LFP)，也就是最小不動點的一階邏輯表達，也就說存在某個多項式時間基于LFP的算法。但是該結(jié)論同K-SAT的某些統(tǒng)計性質(zhì)矛盾。”但他也表示自己的知識不足以評價甚至看懂這篇論文。 Vinay Deolalikar是否真的解決了計算機科學界目前的最大問題呢？讓我們拭目以待。如果你看懂了這篇論文，請與我們聯(lián)系。  Vinay Deolalikar，1971年出生于印度新德里，1994年在孟買印度理工學院獲得電機工程碩士學位，1999年在南加州大學獲得電機工程和數(shù)學博士學位。他的研究興趣是數(shù)論、代數(shù)幾何及其在編碼理論中的應用，機器學習與數(shù)據(jù)挖掘及其在信息管理中的應用，數(shù)理邏輯，隨機過程，統(tǒng)計學，數(shù)字通信等。他在惠普研究院網(wǎng)站上的個人網(wǎng)頁是：http://www.hpl.hp.com/personal/Vinay_Deolalikar http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated.pdf |
回復此樓» 猜你喜歡
309求調(diào)劑
已經(jīng)有9人回復
-
環(huán)境科學與工程334分求調(diào)劑
已經(jīng)有4人回復
-
085404求調(diào)劑，總分309，本科經(jīng)歷較為豐富
已經(jīng)有6人回復
-
285求調(diào)劑
已經(jīng)有5人回復
-
求化學調(diào)劑
已經(jīng)有7人回復
-
材料工程專碩求調(diào)劑
已經(jīng)有4人回復
-
317求調(diào)劑
已經(jīng)有10人回復
-
318求調(diào)劑
已經(jīng)有4人回復
-
化學308分調(diào)劑
已經(jīng)有3人回復
-
一志愿河北工業(yè)大學0817化工278分求調(diào)劑
已經(jīng)有18人回復
» 本主題相關(guān)價值貼推薦，對您同樣有幫助:
- 蛋白純化
已經(jīng)有7人回復
- 問個工作職稱的翻譯問題！在像中科院等這樣的 下屬研究所里 助理研究員 怎么翻譯
已經(jīng)有9人回復
- HP惠普SimpleSave移動硬盤文件
已經(jīng)有2人回復
- 惠普微型計算機主機型號：HSTNC-002L-TC怎么用
已經(jīng)有7人回復
- 求研究員職稱證書樣式
已經(jīng)有7人回復
- 中國科學院青島生物能源與過程研究所模擬仿真團隊“百人計劃”蘭崢崗研究員現(xiàn)公開招聘
已經(jīng)有3人回復
- 請問北京生命科學研究所助理研究員一個月稅前收入多少呀？
已經(jīng)有6人回復
- 中國科學院生命科學研究院孫中生課題組招聘助理研究員
已經(jīng)有6人回復
- 【原創(chuàng)】新加坡化學與工程科學研究所(ICES) 招募項目研究員
已經(jīng)有12人回復
- 【轉(zhuǎn)帖】中國科學院化學研究所韓布興研究員催化方面的文章發(fā)表在最新《science》上
已經(jīng)有71人回復
beijiguang6327
鐵蟲 (小有名氣)
- 應助: 0 (幼兒園)
- 金幣: 3963
- 帖子: 133
- 在線: 67.5小時
- 蟲號: 590110
- 注冊: 2008-08-31
- 性別: GG
- 專業(yè): 數(shù)論
2樓2010-08-11 09:29:30
3樓2010-08-12 00:03:37
sybase
鐵蟲 (正式寫手)
- 應助: 0 (幼兒園)
- 金幣: 596.8
- 帖子: 327
- 在線: 31.7小時
- 蟲號: 615504
- 注冊: 2008-10-01
- 性別: GG
- 專業(yè): 巖土與基礎(chǔ)工程
4樓2010-08-12 18:09:40
coffee999
金蟲 (著名寫手)
- 應助: 6 (幼兒園)
- 金幣: 3697.7
- 散金: 3247
- 紅花: 8
- 帖子: 2331
- 在線: 459.6小時
- 蟲號: 443077
- 注冊: 2007-10-27
- 專業(yè): 計算機網(wǎng)絡(luò)
5樓2010-08-13 08:37:13
liang85
木蟲 (正式寫手)
- 應助: 0 (幼兒園)
- 金幣: 1973.8
- 帖子: 708
- 在線: 48.8小時
- 蟲號: 279686
- 注冊: 2006-09-16
- 性別: GG
- 專業(yè): 代數(shù)學
6樓2010-08-13 09:34:25
7樓2010-08-28 12:32:58
MSTK
金蟲 (著名寫手)
- 應助: 2 (幼兒園)
- 金幣: 1395.9
- 散金: 1282
- 紅花: 2
- 帖子: 1102
- 在線: 932.9小時
- 蟲號: 494452
- 注冊: 2008-01-13
- 性別: GG
- 專業(yè): 計算機網(wǎng)絡(luò)
8樓2010-08-29 22:24:49
BIAOXYZ
木蟲 (著名寫手)
吃貨懶貨
- 應助: 9 (幼兒園)
- 金幣: 6072.6
- 散金: 9
- 紅花: 2
- 帖子: 1317
- 在線: 574小時
- 蟲號: 1036421
- 注冊: 2010-06-05
- 性別: GG
- 專業(yè): 信息安全
9樓2010-09-28 22:51:40
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 學員Z0bAMw 的主題更新
| 9 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 生物技術(shù)與工程 +4 | 1294608413 2026-03-25 | 5/250 |
|
|---|---|---|---|---|
|
[考研] 材料與化工328分調(diào)劑 +9 | 。，。，。，。i 2026-03-23 | 9/450 |
|
|
|
[考研] 349求調(diào)劑 +6 | 李木子啊哈哈 2026-03-25 | 6/300 |
|
|
|
[考研] 2026年華南師范大學歡迎化學，化工，生物，生醫(yī)工等專業(yè)優(yōu)秀學子加入！ +3 | llss0711 2026-03-28 | 6/300 |
|
|
|
[考研] 339求調(diào)劑，想調(diào)回江蘇 +6 | 烤麥芽 2026-03-27 | 8/400 |
|
|
|
[考研] 081200-314 +3 | LILIQQ 2026-03-27 | 4/200 |
|
|
|
[考研] 340求調(diào)劑 +5 | jhx777 2026-03-27 | 5/250 |
|
|
|
[考研] 085600，材料與化工321分，求調(diào)劑 +9 | 大饞小子 2026-03-27 | 9/450 |
|
|
|
[考研] 298調(diào)劑 +3 | jiyingjie123 2026-03-27 | 3/150 |
|
|
|
[考研] 材料求調(diào)劑 +5 | .m.. 2026-03-25 | 5/250 |
|
|
|
[考研] 0703化學一志愿南京師范大學303求調(diào)劑 +3 | zzffylgg 2026-03-24 | 3/150 |
|
|
|
[考研] 求調(diào)劑323材料與化工 +7 | 1124361 2026-03-24 | 7/350 |
|
|
|
[考研] 325求調(diào)劑 +3 | Aoyijiang 2026-03-23 | 3/150 |
|
|
|
[考研] 085601求調(diào)劑總分293英一數(shù)二 +4 | 鋼鐵大炮 2026-03-24 | 4/200 |
|
|
|
[考研] 303求調(diào)劑 +6 | 藍山月 2026-03-25 | 6/300 |
|
|
|
[考研] 07化學303求調(diào)劑 +5 | 睿08 2026-03-25 | 5/250 |
|
|
|
[考研] 考研一志愿蘇州大學初始315（英一）求調(diào)劑 +3 | sbdksD 2026-03-24 | 4/200 |
|
|
|
[考研] 292求調(diào)劑 +4 | 鵝鵝鵝額額額額?/a> 2026-03-24 | 4/200 |
|
|
|
[考研] 277分求調(diào)劑，跨調(diào)材料 +3 | 考研調(diào)劑lxh 2026-03-24 | 3/150 |
|
|
|
[考研] 一志愿山東大學藥學學碩求調(diào)劑 +3 | 開開心心沒煩惱 2026-03-23 | 4/200 |
|