 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 9 | 1/1 | 返回列表 |
| 查看: 2096 | 回復: 8 | |||
[交流]
【分享】惠普研究員稱已解決計算機科學第一難題 已有8人參與
|
|
轉自：http://news.cnblogs.com/n/70425/ 這幾天惠普新聞不斷。其實技術人員更應該關心的，不是那個CEO的緋聞女郎是否漂亮，CEO是否因公司政治蒙冤下臺，而是另一件可能會名垂青史的大事：一位名為Vinay Deolalikar的70后印度籍惠普研究員8月6日在自己的網站發(fā)布了一篇名為“P is not equal to NP”的論文（點擊下載），也就是說，他認為自己證明了P不等于NP！ 學過計算機科學理論的人都應該知道，計算機科學中有一個天字第一號問題一直沒有解決，引得無數圖靈獎得主和頂級計算機科學家競折腰，這個圣杯就是P/NP問題。事實上，這個問題也位列Clay數學研究所重金征解的七大數學難題之首，與我們凡夫俗子也多少知道的黎曼假設和龐加萊猜想并列。解決其中任何一道難題，都可以得到100萬美元獎金。其中，龐加萊猜想已被我們時代最偉大的Geek格里戈里•佩雷爾曼于2002年解決。 簡單的說，P問題是指能找到迅速（準確地說是多項式時間內）解決算法的問題，P是Polynomial（多項式）時間的第一個字母。而NP問題，是指這個問題的解能夠迅速（準確地說是在多項式的時間里）猜測并驗證，但是很難找到，NP是Nondeterministic Polynomial （非確定多項式）的首字母縮寫。所以，P=NP？問題實際上是要證明或者推翻，P問題和NP問題不等價。由于NPC（NP-Complete）問題的存在，學術界普遍認為P不等于NP，但始終無法給出令人滿意的證明。 現在，Vinay Deolalikar宣布自己摘取了這項桂冠。他已經將論文發(fā)給多位各個領域的頂尖專家進行同行評審。目前尚沒有得到任何正式的確認。不過，這個問題的提出者、圖靈獎得主Stephen Cook評論，（Deolalikar的）“聲明看上去比較嚴肅”。 著名的計算理論博客、佐治亞理工學院計算機科學教授Dick Lipton也發(fā)表文章簡單解釋了論文的思路，認為這項工作是嚴肅的。Lipton在文中說，Deolalikar是通過有限模型理論搭橋，引出反證，用到了Moshe Vardi (1982)和Neil Immerman (1986)的結論。 8月9日，Lipton又綜合已有的對論文的評論，發(fā)表了新的文章，認為證明肯定存在錯誤，但他又表示，這是任何突破性研究都無法避免的。該證明的策略是否證明，存在的問題是否能夠修正，仍然有待研究。 此外，猶他大學計算機學院的助理教授Suresh Venkatasubramanian通過Google Docs（鏈接,可能無法訪問）來討論這一證明，充分利用集體智慧，你也可以加入！文檔本身應該是LaTeX格式的。 袁泳在Twitter上分析了Deolalikar的思路，“是通過編碼K-SAT構造某種有序結構。如果NP=P，那根據Vardi的定理，K-SAT能用FO(LFP)，也就是最小不動點的一階邏輯表達，也就說存在某個多項式時間基于LFP的算法。但是該結論同K-SAT的某些統(tǒng)計性質矛盾�！钡脖硎咀约旱闹R不足以評價甚至看懂這篇論文。 Vinay Deolalikar是否真的解決了計算機科學界目前的最大問題呢？讓我們拭目以待。如果你看懂了這篇論文，請與我們聯(lián)系。  Vinay Deolalikar，1971年出生于印度新德里，1994年在孟買印度理工學院獲得電機工程碩士學位，1999年在南加州大學獲得電機工程和數學博士學位。他的研究興趣是數論、代數幾何及其在編碼理論中的應用，機器學習與數據挖掘及其在信息管理中的應用，數理邏輯，隨機過程，統(tǒng)計學，數字通信等。他在惠普研究院網站上的個人網頁是：http://www.hpl.hp.com/personal/Vinay_Deolalikar http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated.pdf |
回復此樓» 猜你喜歡
材料與化工（0856）304求B區(qū)調劑
已經有7人回復
-
085600材料與化工調劑
已經有8人回復
-
285求調劑
已經有7人回復
-
317求調劑
已經有7人回復
-
一志愿華中師范化學332分求調劑
已經有3人回復
-
一志愿北京化工大學材料與化工（085600）296求調劑
已經有25人回復
-
一志愿南昌大學324求調劑
已經有9人回復
-
材料科學與工程 317求調劑
已經有7人回復
-
085701環(huán)境工程求調劑
已經有11人回復
-
286分調劑
已經有10人回復
» 本主題相關價值貼推薦，對您同樣有幫助:
- 蛋白純化
已經有7人回復
- 問個工作職稱的翻譯問題！在像中科院等這樣的 下屬研究所里 助理研究員 怎么翻譯
已經有9人回復
- HP惠普SimpleSave移動硬盤文件
已經有2人回復
- 惠普微型計算機主機型號：HSTNC-002L-TC怎么用
已經有7人回復
- 求研究員職稱證書樣式
已經有7人回復
- 中國科學院青島生物能源與過程研究所模擬仿真團隊“百人計劃”蘭崢崗研究員現公開招聘
已經有3人回復
- 請問北京生命科學研究所助理研究員一個月稅前收入多少呀？
已經有6人回復
- 中國科學院生命科學研究院孫中生課題組招聘助理研究員
已經有6人回復
- 【原創(chuàng)】新加坡化學與工程科學研究所(ICES) 招募項目研究員
已經有12人回復
- 【轉帖】中國科學院化學研究所韓布興研究員催化方面的文章發(fā)表在最新《science》上
已經有71人回復
beijiguang6327
鐵蟲 (小有名氣)
- 應助: 0 (幼兒園)
- 金幣: 3963
- 帖子: 133
- 在線: 67.5小時
- 蟲號: 590110
- 注冊: 2008-08-31
- 性別: GG
- 專業(yè): 數論
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è): 巖土與基礎工程
4樓2010-08-12 18:09:40
coffee999
金蟲 (著名寫手)
- 應助: 6 (幼兒園)
- 金幣: 3697.7
- 散金: 3247
- 紅花: 8
- 帖子: 2331
- 在線: 459.6小時
- 蟲號: 443077
- 注冊: 2007-10-27
- 專業(yè): 計算機網絡
5樓2010-08-13 08:37:13
liang85
木蟲 (正式寫手)
- 應助: 0 (幼兒園)
- 金幣: 1973.8
- 帖子: 708
- 在線: 48.8小時
- 蟲號: 279686
- 注冊: 2006-09-16
- 性別: GG
- 專業(yè): 代數學
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è): 計算機網絡
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
相關版塊跳轉
我要訂閱樓主 學員Z0bAMw 的主題更新
| 9 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研]
 304材料求調劑
+5
|
鐘llll 2026-03-26 | 5/250 |
|
|---|---|---|---|---|
|
|
[考研] 材料化工340求調劑 +3 | jhx777 2026-03-30 | 3/150 |
|
|
[考研] 329求調劑，一志愿西北工業(yè)大學，材料工程（085601） +5 | 小小機靈蟲 2026-03-29 | 11/550 |
|
|
|
[考研] 299求調劑 +10 | 15188958825 2026-03-25 | 10/500 |
|
|
|
[考研] 356求調劑 +4 | gysy?s?a 2026-03-28 | 4/200 |
|
|
|
[考研] 356求調劑 +3 | gysy?s?a 2026-03-28 | 3/150 |
|
|
|
[考研] 求調劑 +7 | 爭取九點睡 2026-03-28 | 8/400 |
|
|
|
[考研] 283求調劑 +3 | A child 2026-03-28 | 3/150 |
|
|
|
[考研] 292求調劑 +14 | 鵝鵝鵝額額額額?/a> 2026-03-25 | 15/750 |
|
|
|
[考研] 調劑 +3 | 李嘉圖·S·路 2026-03-27 | 3/150 |
|
|
|
[考研] 一志愿鄭大085600，310分求調劑 +5 | 李瀟可 2026-03-26 | 5/250 |
|
|
|
[考研] 292求調劑 +4 | 求求了收下我吧?/a> 2026-03-26 | 4/200 |
|
|
|
[考研] 調劑 +4 | 柚柚yoyo 2026-03-26 | 4/200 |
|
|
|
[考研]
085602 289分求調劑
+8
|
WWW西西弗斯 2026-03-24 | 8/400 |
|
|
|
[考研] 一志愿天津大學339材料與化工求調劑 +3 | 江往賣魚 2026-03-26 | 3/150 |
|
|
|
[考研] 機械學碩總分317求調劑�。。�！ +4 | Acaciad 2026-03-25 | 4/200 |
|
|
|
[考研] 293求調劑 +7 | 加一一九 2026-03-24 | 7/350 |
|
|
|
[考研] 一志愿吉林大學材料與化工303分求調劑 +4 | 為學666 2026-03-24 | 4/200 |
|
|
|
[考研] 生物學學碩求調劑 +7 | 小羊睡著了? 2026-03-23 | 10/500 |
|
|
|
[考研]
 085404電子信息284分求調劑
+4
|
13659058978 2026-03-24 | 4/200 |
|