※ 本文為 npc 轉寄自 ptt.cc 更新時間: 2013-05-31 06:37:35
看板 Gossiping
作者 標題 [爆卦] NP=P被證出來了？
時間 Thu May 30 16:30:54 2013
※註:有電視或媒體有報導者，請勿使用爆卦! 違者視為新聞篇數 超貼新聞劣退
Cornell University(維護的平台arxiv)的某篇標題
A Polynomial Time Algorithm for the Hamilton Circuit Problem
http://arxiv.org/abs/1305.5976
是否已經解決了懸宕數十年的NP=P問題？
如果是真的話CS領域就即將有非常重大的突破，
有人要review看看嗎？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.212
→ :跟我想的一樣 結案1F 05/30 16:31
推 :1122F 05/30 16:31
推 :還是去中華電信划算3F 05/30 16:31
→ :甲八辣4F 05/30 16:31
推 :五樓三歲就會了5F 05/30 16:31
推 :@@6F 05/30 16:31
推 :這個演算法我早就解出來了，只是沒空投稿7F 05/30 16:32
推 :恩恩跟我想的一樣原來我想的沒錯8F 05/30 16:32
推 :N=1 結案9F 05/30 16:32
→ :......10F 05/30 16:32
推 : 要經過驗證吧....11F 05/30 16:32
→ :我去年也有發現 不過我以為是常識 就沒有發表了~~12F 05/30 16:32
→ :N9514F 05/30 16:32
推 :好聳動der標題15F 05/30 16:32
推 :又一堆不懂娤懂的鄉民推文了16F 05/30 16:32
推 :恩恩~跟我去年的筆記完全一樣17F 05/30 16:33
→ :文組表示:NP不是筆電嗎?18F 05/30 16:33
推 :有道理 論文寫得還不錯19F 05/30 16:33
→ :JIZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ20F 05/30 16:33
→ :這題我申請博士班的時候也考過啊，我這樣寫教授卻不給分21F 05/30 16:33
→ :中國人證出來的耶22F 05/30 16:33
推 :嗯嗯 大概跟我的想法差不多23F 05/30 16:34
→ :不對,NB才是筆電XD24F 05/30 16:34
→ :這世界上只有三個人知道這件事，一個是我，一個是當事人25F 05/30 16:34
推 :CC26F 05/30 16:34
→ :害我錯失成名的機會27F 05/30 16:34
→ :最後一個我不認識28F 05/30 16:34
→ :要調出一堆假會的人了29F 05/30 16:34
推 :if N=1 NP=P 結案30F 05/30 16:34
推 :沒錯,我剛剛才從遠傳NP到中華31F 05/30 16:34
推 :BJ4 結案32F 05/30 16:34
推 :令N=133F 05/30 16:34
推 :跟我想的一樣34F 05/30 16:34
推 :靠 這人不是幾個月前才來聽我解說過而已嗎?馬的35F 05/30 16:34
推 :NP=P for N=1 這國中生都會.....36F 05/30 16:35
推 :演算法的課本要改了嗎XD37F 05/30 16:35
→ :我猜應該是有做某些假設讓它可以reduce成msp吧?38F 05/30 16:35
→ :令P=0，NP=P 結案39F 05/30 16:35
推 :他的證法有稍微繞一小圈不過還可以啦40F 05/30 16:35
推 :石神教授表示:41F 05/30 16:36
→ :3=8比較厲害42F 05/30 16:37
噓 :arxiv是人人都可以上傳的..上面還有很多篇黎曼猜想的"證明"43F 05/30 16:37
→ :閱 和我想的一樣~44F 05/30 16:37
推 :快推~~~跟我想的一樣45F 05/30 16:38
推 :我早就想出來了 只是懶的上傳46F 05/30 16:38
推 :黑壓 跟我想的一個模一個樣47F 05/30 16:39
推 :No Problem = Problems48F 05/30 16:39
噓 :014=0都比這屌49F 05/30 16:39
推 :跟我想的一樣50F 05/30 16:39
推 :某些步驟不夠漂亮，不知道會不會被challenge51F 05/30 16:40
→ :一堆神人52F 05/30 16:40
推 :This is a 片53F 05/30 16:40
推 :推 turbomons:No Problem = Problems54F 05/30 16:41
推 :Nice play = play55F 05/30 16:41
推 :Nice job=job56F 05/30 16:42
→ :這證明非常容易，單剩下的空白不夠寫，所以就不寫了? XD57F 05/30 16:42
推 :重點是這篇有通過審核嗎,這標題審的人一定拿放大鏡仔細抓錯58F 05/30 16:43
推 :nice person= person59F 05/30 16:43
推 :NP=P , 當P不等於0時 N=1 , 當P=0時 N為任意數 解完60F 05/30 16:43
噓 :有一行寫錯了 我先不講 留給大家思考一下61F 05/30 16:43
推 :NPtt = Ptt62F 05/30 16:44
推 :China的paper要用存疑的態度來看...63F 05/30 16:44
→ :arxiv是Cornell維護的平台 不是表示這篇是Cornell做的64F 05/30 16:45
感謝告知，不過有人要review嗎？很想知道正確性XD
推 :Nice Porn = Porn65F 05/30 16:45
※ 編輯: wheels 來自: 140.112.28.212 (05/30 16:47)[轉寄] Re: [新聞] HP研究員聲稱證明P!= NP - FW板 - Disp BBS
![[圖]]()
最新進展:P!=NP證明引發許多疑問 惠普研究所首席科學家Vinay Deolalikar聲稱證明了P!= NP。一時激起了千層浪，他 的證明引發了廣泛的關注和熱烈的討論，甚至《自然》網站[註一]也關注了此事的進 展。其他數學家已經從他的原始論文中發現了很多小錯誤，提出了幾個還沒有解決的 大問題（該 ...
![[圖]](http://i.disp-tech.com/web/s2/i.disp-tech.com/disp_displogo200.png)
推 :Nano Penis = Penis67F 05/30 16:46
推 :這篇掛大 XD68F 05/30 16:47
推 : 怎麼不拿去給教授review 教授們應該都會很有興趣吧70F 05/30 16:49
→ :這是被認為很適合拿去問外星人的科學問題71F 05/30 16:49
→ :每年都有人投 但是有能力撐的過檢驗的到目前沒有
→ :每年都有人投 但是有能力撐的過檢驗的到目前沒有
噓 :殺小朋友73F 05/30 16:51
推 :嫌疑犯X74F 05/30 16:51
→ :其實我早就證出來了，只是ptt推文太短寫不下75F 05/30 16:51
→ :如果正確的話 真的科科76F 05/30 16:53
推 :中國人好強~~~~~77F 05/30 16:53
推 :是真的也太猛了吧78F 05/30 16:54
哈密顿图判定问题多项式时间算法专题研讨会成功举行_XinwenJiang_新浪博客 哈密顿图判定问题多项式时间算法专题研讨会成功举行_XinwenJiang_新浪博客,XinwenJiang, ...
推 :真的話 也太強80F 05/30 16:55
推 :ptt CS king 這我8歲就會了81F 05/30 16:56
推 :參考資料 都是來自自己!! 不是神人就是牛皮82F 05/30 16:56
推 :不虧是Cornell..83F 05/30 16:59
推 :ref只有2篇是別人的，其它都是自己的...84F 05/30 16:59
推 :推文寫不下，還是算了85F 05/30 17:00
推 :有點強，可怕86F 05/30 17:01
→ :如果是真的 這真的很可怕87F 05/30 17:01
推 :不知道正確性如何，不過真的能證出來一定有諾貝爾獎吧88F 05/30 17:02
推 :跟之前據說推翻相對論的那個類似啊 都cite自己的 後來也不89F 05/30 17:02
→ :了了之
→ :了了之
→ :這問題有趣的地方 就是每年都有不少論文而且正反結果都有91F 05/30 17:02
→ :可能沒有諾貝爾 大概是圖靈獎92F 05/30 17:03
噓 :扯諾貝爾的會不會太好笑了點 要也是非爾茲獎93F 05/30 17:03
→ :誰證出來應該是穩拿 Turing Award... 但有那麼容易嗎94F 05/30 17:04
推 :諾貝爾獎哪來CS領域, 要也是turing award95F 05/30 17:04
Hamilton Circuit - ott板 - Disp BBS
![[圖]]()
![[圖]]()
![[圖]]()
Circuit 經過圖上各處的一條環狀路線。在圖論中，Circuit常與Cycle這個字混用，不過Circuit比較強調「經過圖上各處」這件事情。 下面是要介紹的內容： 一、以邊為主： Euler Circuit：經過圖上所有邊剛好一次的環。 Euler Trail：經過圖上所有邊剛好一次的路 ...
![[圖]](http://i.disp-tech.com/web/s2/www.suffolkmaths.co.uk/pages_Maths_20Projects_Projects_0Project_20Images_Hamilton.jpg)
![[圖]](http://i.disp-tech.com/web/s2/mathworld.wolfram.com/images_eps-gif_HamiltonianPlatonicCycles_751.gif)
![[圖]](http://i.disp-tech.com/web/s2/3.bp.blogspot.com/_zUbnTFdqWyg_TGAeo1OxMmI_AAAAAAAAAFA_4MlUdwPvuAw_s1600_800px-P_np_np-complete_np-hard.svg.png)
→ :Turing Award是穩拿的 廢話97F 05/30 17:06
推 :我的答案跟小當家一樣98F 05/30 17:06
推 :有地方有錯 我晚點寄信給作者99F 05/30 17:08
→ :個人是認為, 這問題留到最後由外星人來開示的可能性不小100F 05/30 17:08
推 :諾貝爾表示:這跟我無關0.<101F 05/30 17:08
推 :ott你只貼Hamilton Circuit NPC的問題多的是XDD102F 05/30 17:08
→ :現在在念的Facility Location跟Independent Set都是QQ
→ :這個證出來不只有錢...turing award也鐵拿..
推 :看最後一段..他還有東西沒解決...
→ :所以他Abstract那邊只寫Our result "implies" NP=P
→ :現在在念的Facility Location跟Independent Set都是QQ
→ :這個證出來不只有錢...turing award也鐵拿..
推 :看最後一段..他還有東西沒解決...
→ :所以他Abstract那邊只寫Our result "implies" NP=P
推 :我告訴你 1=2 那 1+2=?107F 05/30 17:38
→ :幼稚園不是就教過了?108F 05/30 17:38
→ :reference 12篇有10篇的都是自己的 ....109F 05/30 17:40
推 :微微震撼一下 接著無感110F 05/30 17:52
噓 :看這篇就知道八卦板果然一堆魯蛇111F 05/30 17:54
推 :八卦是七成鄉民連p,np問題是啥都不懂112F 05/30 17:55
推 :證出來拿十個圖靈不為過113F 05/30 18:18
推 :真的證出來的話就代表千千萬萬個明星裸照準備流出了114F 05/30 18:36
推 :國防科學技術大學？ 這甚麼等級的啊 ?115F 05/30 18:56
推 :有些地方不太嚴謹 需要在潤色一下116F 05/30 18:58
→ :獎金 100w鎂 嗎?117F 05/30 19:15
→ :其實早就出來了 但重點是誰提出來的才會被接受...118F 05/30 20:02
→ :非常好 台灣老闆要開幾K請119F 05/30 21:39
推 :真假 若真 演算法教科書要重寫了吧120F 05/30 21:52
推 :期末考會不會考阿121F 05/30 21:58
推 :http://www.win.tue.nl/~gwoegi/P-versus-NP.htm122F 05/30 22:35
→ :幾乎每年都會有人跳出來說自己證明了這個問題...but...XDD
→ :幾乎每年都會有人跳出來說自己證明了這個問題...but...XDD
噓 :不懂別裝懂，證出一個NPC=P，所有NPC都解決了124F 05/31 01:44
→ :我只看過P=NPC的，那個叫做外掛125F 05/31 03:44
--
回列表(←)
分享