過客的日記

上週對於全世界的計算機科學家最大的新聞
就是有某位在HP Lab工作的印度學者Vinay Deolalikar
發表了一篇正式的證明
標題很簡單
就是NP!=P (NP不等於P)
原稿在這裡


這個證明之所以會這樣轟動
是因為它有Steve Cook(計算機科學大師, Turing Award得主)的背書:
"this looks like a serious effort."

什麼是NP? 什麼是P?
簡單來說NP和P各是一堆問題的集合
如果一個問題屬於P, 表示我們已經找到一個有效率的方式來解決這個問題
如果一個問題屬於NP, 表示我們目前尚未找到好的方式來解問題
(我知道這樣講有很多語病, 不過就不用跟我計較了 ...)

NP是否等於P在計算機科學以及應用數學領域是一個極為重要的問題
克雷數學研究所曾經把這個問題列為七個千禧年大獎難題之一
只要解開的人就可以獲得一百萬美元的獎金

但是麻煩的地方在於
這些屬於NP的難題
我們雖然目前尚未找到好的辦法解題
但是也沒有辦法否定一定找不到好方法

簡單來說
如果有一個人可以找到有效率的方法來解決NP之中的問題
那NP=P;
如果有人可以證明絕對找不到
那NP!=P

因為數十年來世界上最聰明的計算機科學家
也無法找到好的辦法來解決NP之內的問題
所以大家普遍上相信NP!=P
而Vinay Deolalikar的證明等於是將大家長久以來
"相信但是無法證明"的陳述事實化

如果他是對的
毫無疑問是一件極為偉大的成就
但是對於現實不會有太大的改變
因為這是大家長久以來內心相信的事實
反過來說
如果有人證明NP=P
那世界可能就會崩潰了
舉例來說
一些我們長久以來認為很難被破解的密碼學系統
可能一夕之間瓦解

Richard J. Lipton是一位計算機科學大師
他上週末花了很多時間閱讀Vinay Deolalikar的證明
總之他暫時還不能確定這個證明的正確性
連結在這裡
不過他說整個證明的方式是這樣的
如果NP=P
1. 那某個陳述D就會是對的
2. 但是D可被證明是錯的

所以如果1.及2.都成立
D會是錯的, 那NP!=P成立
同理
如果1.或2.有一樣是錯的
那整個證明就瓦解了

而整個證明的重點在於
Vinay Deolalikar用了finite model theory來定義何謂"有效率"的演算法
這是一般計算機科學家沒有想過的;
同理他也利用了統計物理的方式來證明上面說的2.陳述

這兩種辦法都是全新的概念
所以即使Vinay Deolalikar是錯的
但是這個證明對後面的人毫無疑問會有很多啟發

至於證明的正確性與否
就有待時間來審視了