作者ypchen (真實的虛幻和虛幻的真實)
站內PhD
標題[資訊] P != NP has been claimed to be proved.
時間Tue Aug 10 23:55:26 2010
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
1F：推 andan:大驚! 如果是真的, 那就太神了...一個人獨力證完... 08/11 00:13
3F：→ chucheng:102 頁 …XD 08/11 00:34
4F：→ qtzbbztq:...有人可以用白話解釋一下嗎:p 08/11 01:00
5F：→ kusobike:電洞參雜不等於電子電洞參雜 08/11 01:13
6F：→ emitter:P階層等於N乘以P 08/11 01:14
7F：→ kusobike:單字母P不等於雙字母NP 08/11 01:15
8F：推 zhewei:應該是P不等於NP 08/11 01:18
9F：→ Aipr:白話: 有些很難的問題, 被證明真的不是普通的難 08/11 01:30
10F：推 costbook:Aipr的解釋真是一針見血 08/11 01:33
11F：推 vicptt:Wow... 真的證出來了嗎? 有被確認過嗎? 真是太厲害了... 08/11 01:48
12F：→ howshou: 有些計算機很難快速算出的問題, 不存在快速的解法。 08/11 01:49
13F：→ howshou:看不懂沒關係, 不過若是證明成功, 可以說他是計算機科學 08/11 01:54
14F：→ howshou:領域, 40年來最聰明的人。 08/11 01:55
15F：推 micklin:樓上, 沒人會這樣說 08/11 03:17
16F：→ micklin:並不是40年來, 全部計算機科學的人都在想這個問題. 08/11 03:19
17F：→ micklin:PhD們少了一個題目可做, 但多了一堆題目可以做 08/11 03:20
18F：→ howshou:我是寫給不懂的人看的, 只是想表示這個證明有多厲害。 08/11 03:55
19F：推 lingon:Intuitive, but still depressing...(more $ to q.comput?) 08/11 04:22
20F：推 CryAll:膜拜ing... 08/11 08:39
21F：推 AppleFox:@@" 真的假的 真的被證出來了 08/11 09:38
23F：推 ggk:這證明了之後 就是叫大家不用再試著找最佳解法了?? 08/11 12:20
24F：→ qtzbbztq:XD 其實我問了問題後就要到處找了 也是看到樓上的網頁 08/11 13:12
25F：→ qtzbbztq:大概知道這個意思是甚麼了 08/11 13:12
26F：推 hcchan:教演算法的用力推 08/11 15:35
27F：推 hcchan:事實上早就在猜p!=np 若被證出 p=np 那才真的恐怖 08/11 15:38
28F：推 gorhow:推樓上 如果有人能證出 P=NP 就是神了 = = 08/11 15:49
29F：推 swatch3484:怎麼讓我想到 當地球停止轉動電影的梗 外星人寫 XX=XX 08/11 15:58
30F：→ Azraelx:密碼學家多傾向相信P!=NP 很多密碼系統基於P!=NP寫證明 08/11 16:38
31F：→ Azraelx:如果P=NP 會有很多密碼系統是錯的XD 08/11 16:38
32F：→ Azraelx:另外 面對NP問題 現行常見作法是找近似解(approximation) 08/11 16:40
33F：→ Azraelx:近似解概念是 雖然做不到最佳 但只差最佳解多少(例如1倍內 08/11 16:42
34F：→ Azraelx:假設這篇證明是對的 作者對CS界的貢獻會很巨大 08/11 16:45
35F：→ Azraelx:以上不知有沒有說錯 有錯的話請指正~ 08/11 16:46
36F：推 khwang0:樓上：密碼系統只會不安全，不會錯。如果怕NP=P的話，可以 08/11 21:31
37F：→ khwang0:看無條件安全的系統或量子密碼學 08/11 21:31
38F：→ Azraelx:應該說安全證明是錯的 也就是不知安不安全 謝謝樓上指正XD 08/11 22:34