Finite Playground

To verify is human; to prove, divine.

Vinay Deolalikar 證明了 P 不等於 NP?

3 Comments

二零一零年八月六日, 也許這將會成為一個重要的日子.

就在這一天, HP 實驗室的 Vinay Deolalikar 宣布了他解決了 P/NP 問題. 很不嚴謹的問題敘述如下:

是否所有能夠迅速檢查正確性的問題, 都能夠被迅速的計算?

P 代表著所以能夠被迅速計算 (行話來說, 就是指在多項式時間內) 的問題的集合, 而 NP 代表能夠被迅速檢查的問題的集合. 這問題屬於計算理論這門學問, 其中 P 在 NP 之中是個已知的結果. 幾十年來, 許多人投注心力於證明或反證這兩類問題是否一樣, 也有許多人宣稱他們證明, 反證, 甚至是說明這個問題無法解決, 直到目前為止都沒有一個令人接受的答案.

Vinay Deolalikar 是 HP 實驗室的研究員, 他曾經發表過資訊理論相關的論文, 以背景來看並非對問題的歷史和難度一無所知. 此外從論文的寫作來看, 是相當正經的, 也有最上層的證明簡述, 以及提供他對此證明正確的基本辯證, 經過相當的用心寫出, 希望能夠真正解決掉此世紀難題. 此外許多新觀念的引進, 增添了此證明的可信度, 即使沒有成功, 也給其他人多了許多繼續研究的方向.

Dick Lipton 在他的 blog 上面簡述了證明的大綱, 另外網路上還有一堆相關的討論, 希望在不久的將來, 就能知道這個證明的正確與否, 以及提供更清楚, 完整的證明方式.

我們這些小毛頭學生, 就等著看吧!

Author: hcsoso

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.

3 thoughts on “Vinay Deolalikar 證明了 P 不等於 NP?

  1. 目前看起來似乎是有問題…
    已經慢慢 pinpoint 出漏洞的所在了.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s