[資訊] P != NP has been claimed to be proved.

看板PhD作者 (真實的虛幻和虛幻的真實)時間14年前 (2010/08/10 23:55), 編輯推噓15(15推 0噓 23→)
留言38則, 20人參與, 最新討論串1/3 (看更多)
Dear Colleagues, Please allow me to share this intriguing (and probably very important) news with you: Vinay Deolalikar from HP Labs claimed to prove that P != NP http://gregbaker.ca/blog/2010/08/07/p-n-np/ Prof. Stephen Cook said “This appears to be a relatively serious claim to have solved P vs NP.” -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.235.151
推
08/11 00:13, , 1F
大驚! 如果是真的, 那就太神了...一個人獨力證完...
08/11 00:13, 1F
推
08/11 00:34, , 2F
08/11 00:34, 2F
→
08/11 00:34, , 3F
102 頁 …XD
08/11 00:34, 3F
→
08/11 01:00, , 4F
...有人可以用白話解釋一下嗎:p
08/11 01:00, 4F
→
08/11 01:13, , 5F
電洞參雜不等於電子電洞參雜
08/11 01:13, 5F
→
08/11 01:14, , 6F
P階層等於N乘以P
08/11 01:14, 6F
→
08/11 01:15, , 7F
單字母P不等於雙字母NP
08/11 01:15, 7F
推
08/11 01:18, , 8F
應該是P不等於NP
08/11 01:18, 8F
→
08/11 01:30, , 9F
白話: 有些很難的問題, 被證明真的不是普通的難
08/11 01:30, 9F
推
08/11 01:33, , 10F
Aipr的解釋真是一針見血
08/11 01:33, 10F
推
08/11 01:48, , 11F
Wow... 真的證出來了嗎? 有被確認過嗎? 真是太厲害了...
08/11 01:48, 11F
→
08/11 01:49, , 12F
有些計算機很難快速算出的問題, 不存在快速的解法。
08/11 01:49, 12F
→
08/11 01:54, , 13F
看不懂沒關係, 不過若是證明成功, 可以說他是計算機科學
08/11 01:54, 13F
→
08/11 01:55, , 14F
領域, 40年來最聰明的人。
08/11 01:55, 14F
推
08/11 03:17, , 15F
樓上, 沒人會這樣說
08/11 03:17, 15F
→
08/11 03:19, , 16F
並不是40年來, 全部計算機科學的人都在想這個問題.
08/11 03:19, 16F
→
08/11 03:20, , 17F
PhD們少了一個題目可做, 但多了一堆題目可以做
08/11 03:20, 17F
→
08/11 03:55, , 18F
我是寫給不懂的人看的, 只是想表示這個證明有多厲害。
08/11 03:55, 18F
推
08/11 04:22, , 19F
Intuitive, but still depressing...(more $ to q.comput?)
08/11 04:22, 19F
推
08/11 08:39, , 20F
膜拜ing...
08/11 08:39, 20F
推
08/11 09:38, , 21F
@@" 真的假的 真的被證出來了
08/11 09:38, 21F
→
08/11 12:18, , 22F
http://ppt.cc/GU19 這裡有解釋問題 光問題就要看半天了....
08/11 12:18, 22F
推
08/11 12:20, , 23F
這證明了之後 就是叫大家不用再試著找最佳解法了??
08/11 12:20, 23F
→
08/11 13:12, , 24F
XD 其實我問了問題後就要到處找了 也是看到樓上的網頁
08/11 13:12, 24F
→
08/11 13:12, , 25F
大概知道這個意思是甚麼了
08/11 13:12, 25F
推
08/11 15:35, , 26F
教演算法的用力推
08/11 15:35, 26F
推
08/11 15:38, , 27F
事實上早就在猜p!=np 若被證出 p=np 那才真的恐怖
08/11 15:38, 27F
推
08/11 15:49, , 28F
推樓上 如果有人能證出 P=NP 就是神了 = =
08/11 15:49, 28F
推
08/11 15:58, , 29F
怎麼讓我想到 當地球停止轉動電影的梗 外星人寫 XX=XX
08/11 15:58, 29F
→
08/11 16:38, , 30F
密碼學家多傾向相信P!=NP 很多密碼系統基於P!=NP寫證明
08/11 16:38, 30F
→
08/11 16:38, , 31F
如果P=NP 會有很多密碼系統是錯的XD
08/11 16:38, 31F
→
08/11 16:40, , 32F
另外 面對NP問題 現行常見作法是找近似解(approximation)
08/11 16:40, 32F
→
08/11 16:42, , 33F
近似解概念是 雖然做不到最佳 但只差最佳解多少(例如1倍內
08/11 16:42, 33F
→
08/11 16:45, , 34F
假設這篇證明是對的 作者對CS界的貢獻會很巨大
08/11 16:45, 34F
→
08/11 16:46, , 35F
以上不知有沒有說錯 有錯的話請指正~
08/11 16:46, 35F
推
08/11 21:31, , 36F
樓上：密碼系統只會不安全，不會錯。如果怕NP=P的話，可以
08/11 21:31, 36F
→
08/11 21:31, , 37F
看無條件安全的系統或量子密碼學
08/11 21:31, 37F
→
08/11 22:34, , 38F
應該說安全證明是錯的 也就是不知安不安全 謝謝樓上指正XD
08/11 22:34, 38F
‣ 更多 ypchen 的文章
文章代碼(AID): #1CONPnxs (PhD)
‣ 更多 ypchen 的文章
文章代碼(AID): #1CONPnxs (PhD)