Finite Playground

To verify is human; to prove, divine.


3 Comments

Vinay Deolalikar 證明了 P 不等於 NP?

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

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

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

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

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

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

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


2 Comments

IMO 2009 Q6

從 Terence Tao 陶哲軒的 blog “What’s New” 上看到的,
花了大約一個小時找對了解題的方向, 就沒有再做下去了,
設計的很精良的題目, 有興趣可以試試看!

A = \{a_1, \ldots, a_n\} 皆為相異正整數, 令 M = \{m_1, \ldots, m_{n-1}\} 為正整數, 但其中不包含 s = \sum_i a_i. 有一隻蚱蜢, 從數線原點開始往右跳 n 步, 步伐長正好是 A 的某種排序.

請證明聰明的蚱蜢可以找出一種 A 的排序使得牠跳的每一步都不會落在 M 中的任一點上.


Leave a comment

Guessing numbers with wrong answers

在 Math Overflow 上看到的有趣問題!
假設給定平常常見的猜數字遊戲:
在 1~1000 當中選擇一個數字, 請問最少要多少次可以猜出來?
有經驗的玩家一定知道切半法是最好的答案, 因此是 10 次.

這是, 若我們假設回答問題的人會有一次的機會回答錯誤,
請問這時猜的人最少要多少次才能猜對?