二零一零年八月六日, 也許這將會成為一個重要的日子.
就在這一天, HP 實驗室的 Vinay Deolalikar 宣布了他解決了 P/NP 問題. 很不嚴謹的問題敘述如下：
是否所有能夠迅速檢查正確性的問題, 都能夠被迅速的計算?
P 代表著所以能夠被迅速計算 (行話來說, 就是指在多項式時間內) 的問題的集合, 而 NP 代表能夠被迅速檢查的問題的集合. 這問題屬於計算理論這門學問, 其中 P 在 NP 之中是個已知的結果. 幾十年來, 許多人投注心力於證明或反證這兩類問題是否一樣, 也有許多人宣稱他們證明, 反證, 甚至是說明這個問題無法解決, 直到目前為止都沒有一個令人接受的答案.
Vinay Deolalikar 是 HP 實驗室的研究員, 他曾經發表過資訊理論相關的論文, 以背景來看並非對問題的歷史和難度一無所知. 此外從論文的寫作來看, 是相當正經的, 也有最上層的證明簡述, 以及提供他對此證明正確的基本辯證, 經過相當的用心寫出, 希望能夠真正解決掉此世紀難題. 此外許多新觀念的引進, 增添了此證明的可信度, 即使沒有成功, 也給其他人多了許多繼續研究的方向.
Richard Lipton 在他的 blog 上面簡述了證明的大綱, 另外網路上還有一堆相關的討論, 希望在不久的將來, 就能知道這個證明的正確與否, 以及提供更清楚, 完整的證明方式.
我們這些小毛頭學生, 就等著看吧!
文章取自 Chicken's Finite Playground
相關連結：
本週熱門新聞
-
利用近距離無線通信技術將手機及可穿戴式感測器終端等與智慧電話連接起來，實現新的功能。最近，以此為目標的行動正在展開。其中備受關注的近距離無線方式是「ANT」和「Bluetooth LE」。為了在各種便攜終端上採用這些技術，手機、手錶及保健電子產品的廠商開始加快行動。
-
美國黑色星期五銷售旺季期間智慧型手機及平板電腦大賣，帶動加速度計（Accelerometer）、陀螺儀（Gyroscope）等微機電晶片（MEMS）銷售，市場普遍看好明年MEMS晶片銷售，將因智慧型手機及平板電腦的出貨量放大而出現爆炸性成長。
-
您曾想過像科幻片中，以意念控制賽車的情景嗎？您曾想過與朋友比賽誰的念力比較強嗎？ 大寶科技與國立勤益科技大學電資學院合作開發出以念力控制的賽車，使用者只要戴著一副意念耳機，就可以用專心的程度來控制賽車的速度。
-
視線追蹤系統(eye gaze tracker)的目的是要偵測眼睛注視的方向，藉由追蹤眼睛視線，可以明確知道使用者感興趣的事物，因此視線追蹤一直是一個有趣以及重要的研究議題。視線追蹤系統的應用很廣，早期的系統是發展在一個實驗室或者是在一個受控制的環境之下使用，來避免外界的不確定的... -
使用活動假牙黏著劑該注意哪些事情？三軍總醫院口腔贗復科主任王宜斌說，使用全口、半口活動假牙一段時間，牙床會逐漸萎縮，假牙也特別容易鬆脫，這樣的族群在進行社交活動時可以考慮使用假牙黏著劑。不過使用黏著劑時要避免飲用過熱湯湯水水，過熱高度容易溶解黏著劑，導致假牙鬆脫。
討論基本定音。論證中對 reduction 映射下的 polylog-parametrizability 是否依然有效沒有證明。 只能得出結論是 一旦這東西有效，那麼才有 P!=NP。 而映射下的有效性本身就貌似是 P vs NP 的一種…… 最後變成循環了嗎？
回覆刪除Fatal Flaws in Deolalikar’s Proof? http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/ 說明Deolalikar的證明有瑕疵
回覆刪除