TCS 新聞幾則

Ref.: International Congress of Mathematicians 2010, Hyderabad » Prize Winners 2010

ICM 2010 剛宣布了今年度的 Fields Medalists 和 Rolf Nevanlinna Prize 的贏家. Rolf Nevanlinna Prize 今年是頒給了 Daniel Spielman

Daniel Spielman of Yale University, USA, has been chosen for the 2010 Rolf Nevanlinna Prize for smoothed analysis of Linear Programming, algorithms for graph-based codes and applications of graph theory to Numerical Computing.

Daniel Spielman 和 Teng Shang-Hua 共同發明了 smoothed analysis 的概念. 是很厲害沒錯啦, 不過我個人不是很喜歡這個概念. 我第一次聽到這個概念是強者我同學在實驗室的報告. (他跑到 Dartmouth 唸博班, 進入國際標準, 如果我這個待在國內的騙吃騙喝的弱者還輕率地稱他強者, 那就辱沒他了, 希望有一天他能嶄露頭角成為國際級的強者)

不過前一陣子最熱門的理論計算機科學相關新聞應該是HP 研究員 Vinay Deolalikar 號稱解決了 NP!=P 的猜想. 連 BBC News 都報導了這個消息. 不過經過兩個星期的公開討論後, 這個證明已經被駁回了.

這中間當然也牽扯到很多問題, 其中一個問題就是, 花這麼多時間去審查這種論文值不值得!?

這類已解決重大難題的宣言其實並不少見, 費馬最後定理, 哥德巴赫猜想, 還有 P vs. NP 猜想, 都是常常被提到的問題. 主要的原因可能是這些問題的描述都比較簡單, 基本上業餘的數學愛好者就可以看懂這些問題. 所以常常會有些非專業的人號稱解決的這個問題. 這次之所以會受到注目, 原因之一就是因為這是由專家學者提出 Vinay Deolalikar.

不過當然並不是所有的人都這麼看好, Lance Fortnow 似乎是興趣缺缺. 尤其 Russel Impagliazzo 更明白指出這是浪費時間. 當然 Timothy Gowers 和 Terence Tao 可能不這麼認為, 畢竟他們一起推動了 Polymath projects. 對他們來說, 知識分享方式也是一種研究方法的實驗. 對他們來說, 這種互動方式, 能對我們的研究有什麼樣的幫助是更加重要. 就像 Terence Tao 所說的

I think there are several levels to the basic question “Is the proof correct?”:

1. Does Deolalikar’s proof, after only minor changes, give a proof that P {\neq} NP?
2. Does Deolalikar’s proof, after major changes, give a proof that P {\neq} NP?
3. Does the general proof strategy of Deolalikar (exploiting independence properties in random {k}-SAT or similar structures) have any hope at all of establishing non-trivial complexity separation results?

實際上 Polymath1Wiki 有一個條目就是用來討論 Deolalikar 的 P vs NP 論文.

Ref.: MIT News: 3 questions: P vs. NP
Ref.: BLOG@CACM: A Tale of A Serious Attempt At P≠NP, Richard J. Lipton
Ref.: P vs. NP，我们从过去的一周中学到了什么？ - Apple4.us