Re: [其他] 見證奇蹟的時刻 NP=P

[mo2 (公雞)]

※ 引述《tailsice (tailsice)》之銘言：
: http://arxiv.org/abs/1305.5976
: 一篇在國外發表的非正式論文
: 尚未被審稿通過的文章
: 但是已經引起強烈的討論
: 如果這篇通過，將會撼動整個演算法世界了了

這應該是一位老師 看了他的部落格 感覺他滿屌的 XD
1.他研究P=NP已經超過15年
2.2011年他曾經用短短5天時間 否認一篇寫了8年的P≠NP大論文
3.隨機測試他已經跑了好幾年 超過5000萬多筆 他的證明目前還是對的 無一例外

不過話說回來
給定任何圖 可以用多項式時間
就馬上判定有無Hamilton cycle/找到最短Hamilton cycle

請問這對現在生活會造成什麼衝擊??
真的會進入另一個世界嗎?
有沒有比較懂的大大可以講一下 (真的頗好奇!)
謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.250.208.98
※ 編輯: mo2             來自: 60.250.208.98        (05/31 18:40)
推 APM99       :不會  完全沒影響
推 bbenson     :連NP=P 再說什麼都不知道 ~(路過)
→ wohtp       :研究quantum computing的人會發現錢一下子少很多 XD
推 springman   :所有 nondeterministic polynomial 的問題都可以找到
→ springman   :polynomial time 的演算法，這應該是非常大的貢獻。
→ springman   :我們常說 P 是否等於 NP 是最近四十年
→ springman   :computer science 最大的問題。
推 LPH66       :關於 P vs NP 問題可以參考我的 #1GPBcQPe
→ LPH66       :(雖然那邊有一部份篇幅在講踩地雷就是了ww)
→ bbenson     :只有踩地雷看得懂ww
推 recorriendo :Hamilton cycle本身當然沒什麼重要 重點是所有NP問題
→ recorriendo :都可以轉化成Hamilton cycle問題 你證明它可以在多項
→ recorriendo :式時間解出就等於說所有NP問題都可以在多項式時間解
→ sneak       : Hamilton cy https://noxiv.com
→ sneak       : //noxiv.com https://daxiv.com
→ muxiv       : 研究quantum c https://moxox.com