Zero-sum subsets

這個有趣的(小)問題是在 MathOverflow 上看到的。

假設我們有一個有限集合為某個群 (如自然數) 的子集, 滿足底下條件：

任何中的元素都可以寫成另外兩個中元素的和；也就是說令，則。

試證明：中存在一個非空子集使得中所有元素相加為零。

我們稱這樣的子集為零和子集 (zero-sum subset)。

零和字集在加性組合學 (additive combinatorics) 中是個被廣泛研究的主題；例如在一個群當中，若任意給定個元素形成的集合其中都有零和子集，滿足這樣條件最小的，我們稱作 restricted Davenport number。在 Szemeredi 的 “On a conjecture of Erdos and Heilbronn” 中，他證明了

,

其中為的大小。

但是由所謂 sum-full (也就是) 這樣的條件而保證零和子集的存在性，在文獻中卻是沒有看過… 似乎是個很有趣的問題！目前為止只能想到一些標準化為圖論問題的方法，反證了幾個過於樂觀的猜想，卻沒有進一步的結果… 也許需要一些其他的工具來證明。有沒有什麼想法呢？

Vinay Deolalikar 證明了 P 不等於 NP?

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

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

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

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

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

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

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