NP=NP? 從計算到智能的終極問題

你是一, 也是萬! 是剎那, 也是永恆!

Im the Alpha and the Omega,the First and the Last,the Beginning and the End.

--新約.創世紀

二零XX年, 歷史揭開了新的篇章, 計算宇宙中的第一個人誕生了, 這是一個新的紀元. 史稱人工智慧元年。

如果要寫本小說, 我大概會以這樣的句子作為開場。人工智慧開始火熱以來，大眾能夠接觸和理解的文章里各種荒謬和誤導太多。而領域內的學者們又忙於寫論文。學者精英和公眾之間出現了鴻溝。要想通過傳播知識在這個鴻溝之上架起橋樑，科普文章是一種方式。而傳播學告訴我們, 其實公眾更喜歡故事, 如果有一本像樣的科幻小說, 可能比多少篇科普文章更有效。所以寫本關於人工智慧的小說， 是我埋藏很久的一個願望。 但是個人能力時間所限, 這本小說還得等很久， 或許會胎死腹中。 大部頭之外，一些片段思想可以單獨談談， 今天就來說說有關計算和智能的基本問題。

不知道讀者里有多少碼農？ 學計算機的人，都學過關於計算的一般理論。 知道我們把所有計算機要解決的問題，也就是可計算的問題分為大致兩類， 一類是所謂多項式問題P問題， 一類是非多項式問題NP問題。

多項式問題最簡單的是0階，或者1階線性N， 如果複雜度是2階的N平方關係，問題規模一大就玩不轉了。一階二階之間還有個NlogN， 大概是計算機能夠愉快玩耍的邊界。 因為0階，一階過於簡單，二階又有點複雜， 我們觀察到的大部分演算法和技巧， 都是試圖把一個問題搞成NlogN。

而非多項式問題NP問題又有NP, NP hard和NP complete之分， 這兩個概念經常會被人誤解，一個直觀的理解 NP complete問題比NP hard問題更難就是錯誤的。 正確的理解，首先要知道什麼是可計算的問題。

所謂可計算的問題， 就是假設我們找到一個解， 這個解到底對不對， 是可以在P這個量級的計算上判斷的， 如果連這一步都做不到， 那乾脆什麼都做不了。 可以在P計算上判別的問題， 如果問題的求解還找不到一個P演算法。 那就是一個NP問題。 而NP complete問題， 就是NP 裡面最難的一類， 這一類問題是等價的，如果解掉其中一個， 說明所有的NP問題都可以解掉。而NPhard 問題, 可以包括不能用P演算法判斷的問題.

拿圍棋來舉個例子。下圍棋是很難的，想算出下一步該怎麼下，非常非常困難，尤其是一開始布局的時候。 而越到後來，越接近終局，越簡單。收官的階段，計算機早就勝過人了（ 因為人容易出錯， 計算機不會出錯） 到最後 一盤棋下完了，判斷輸贏是很簡單的，誰都會數子。所以下圍棋是個典型的NP 問題 ，也許還是NP complete的（沒查過）。

自NP問題的定義提出以來,無數計算機科學家和數學就試圖在證明NP=P。意思是這些看上去很難的問題, NP問題, 實際上沒有那麼難, 有P多項式的級別的精妙演算法。 如果有這樣的證明, 所有這些可計算的問題都能計算， 世界將是多麼的完美。。。。和無聊啊。

本文站在哲學的高度， 駁斥了P=NP。 NP問題就是沒有P解法，世界才如此的豐富多彩。 為什麼？

還是從計算理論的核心思想談起。 我們經常把人比做計算機。 計算機也被叫做電腦。 從計算的角度來看， 這樣的類比其實正是抓住了問題的本質。 換一個角度， 我們知道人是很聰明的， 所謂聰明體現在那裡，也就是智能是什麼，很多人講不清楚。 我在這裡給聰明或者說智能給一個定義， 所謂真正的聰明或者智能就是能夠建立數學模型。

我們知道大部分動物都是不會數數的， 單憑直覺， 烏鴉（最聰明的鳥類之一）大概能夠數到4， 對烏鴉來說， 他們的世界是0，1，2，3，4，無窮。 而在發明數學之前，人也不是太會數數， 對不會數數的原始人來說，大概也是0，1，2，3，無窮， 比烏鴉還要笨一點。

而一旦發明了數字， 人學會了數數，就走上了與動物不同的不歸路。 我們不光學會了數數， 還發明了加減乘除，也就是計算，我們稱之為發明了數學。隨後計算就變的越來越複雜，數學也就越來越複雜。 而通過物理， 計算和大自然聯繫了起來。所謂物理， 就是用數學公式來描述大自然的一般規律。 我們認為一個事情有沒有理論，是不是掌握髮現了其中的規律， 等同於這個事情能不能用數學公式來描述，能不能建立數學模型。 我們管能建立數學模型的，並且用模型能夠對事實做出預測的叫做科學。

按照以上說法， 我們把這個世界分為兩種， 可能用科學理論精確描述的世界。 不能用科學理論精確描述的世界。 對前一種， 我們非常擅長， 對後一種。。。 我們一直在試圖把後一種轉化為前一種。 就象大家一直在試圖證明P=NP一樣。

能夠用數學描述的世界只佔現實世界的很小一部分。數學理論發展到二十世紀下半段， 發現了所謂混沌現象。 所謂混沌，大概的意思是， 就算我們已經有了數學模型， 按道理就一切盡在掌握中。而實際上， 我們還是掌握不了， 因為混沌是一種非線性系統，其中非常微小的初始條件差別，會導致特別不一樣的結果。 要預測未來， 只能一步一步算， 這種計算還要足夠足夠精確。 時間一久，其實算不過來，也就混沌了。

混沌現象出現，引發了對複雜系統的演化的研究。我們發現 大多數自然，生物，人類社會的現象，都可以歸結為一個複雜系統。 所謂複雜系統， 是從系統的局部，或者某一個時刻，能夠建立數學模型，但是模型是非線性的，一旦開始演化，整體的結果就不可以預期了。 混沌的世界遠比能夠數學建模精確描述的簡單世界更大（簡單是因為只有線性）。

前面把智能，定義為數學建模的能力， 而混沌理論告訴我們，即使建了模也沒有多大用處。 那該怎麼辦？ 在計算機出現之前， 大概有兩條路。 一條路走上了玄學， 之前我們談過的周期律就是這類東西。 一條路叫做概率統計。

還是拿圍棋來舉例說明。從全局來說， 整個圍棋世界是有始有終的，從一個空盤開始落字， 到填滿棋盤，圍棋終將會分出勝負， 棋局就結束了。 理論來說， 圍棋是有個最優的唯一下法的。 所謂上帝一局。 但是從計算複雜理論出發，因為只能算， P又不等於NP， 要想明確算出上帝一局，調動全部現有的計算資源也不夠。計算能力限制了探索問題的邊界， 我們其實沒有辦法找到這個能夠證明是最優的上帝一局。 只有上帝知道。

假設一個智能棋手生活在圍棋的世界， 唯一目的就是下棋。這個圍棋的棋盤很大很大，當然比現有的圍棋棋盤大很多。 而棋手只能看到眼前的一小塊棋，看不到邊界， 那他會怎麼理解世界呢？ 影響棋手的聰明程度一個關鍵是他的記憶能力。因為棋手們會通過總結下棋的歷史來試圖掌握規律，他能記住多大一段歷史，大大影響了他下棋的策略。記憶能力強的，看到的棋局也大，會認為這個世界很複雜。 記憶能力小的,看到的棋局小，極端情況， 假設只能記住之前一步，那麼策略可能就是往有空的地方走。根本夠不上叫一個複雜系統，或者說沒有智能。

而記憶能力比較強的棋手會有什麼樣的策咯？ 我相信他早晚會發現自己處在一個複雜系統中，而且掌控不了全局。只能根據已知的歷史和當前觀察到的範圍做出判斷，把全部未知的東西， 當作隨機。 這些隨機的東西雖然捉摸不定，但是總體上還是有些規律， 於是棋手很可能會發明統計，並且用貝葉斯公式來計算棋局。 他的記憶越多，計算的越多，表現出來的行為模式也就越複雜。 於是就出現了智能。

因此智能的出現可以理解為有記憶和能計算。 智能的門檻是足夠包容一個複雜系統。 在此前提下，計算能力越強， 記憶能力越強， 就更智能。對一個智能體來說，能夠觀察到的世界是有限的， 而世界本身就是一個複雜系統， 因此世界永遠是捉摸不定的，隨機的。 正是這種隨機性， 才讓世界如此豐富多彩。

不管你同不同意， 計算的出現，構成了一個新的宇宙。 足夠複雜的計算可以被當作這個計算宇宙中的智能體 。計算宇宙中的生命, 叫做人工智慧。 P不等於NP， 是這個計算宇宙成立的前提。

以上從哲學觀點說明了P不等於NP，

等等， 本文的標題不是P=NP，而是NP=NP？ 標題沒有寫錯， 這裡想說的是，站在哲學的角度， NP肯定不是P，這個不是問題。（期待學數學的童鞋來暴擊） 我們需要搞清楚的，每個NP會不會有不一樣?

比如圍棋的世界和現實世界等價嗎? 我們如果在計算的世界創造了人工智慧， 他們的世界和現實世界是有所不同，還是完全一樣？ 人工智慧還能夠發明新的世界嗎？

Wolfram的答案是， NP=NP, 他說他已經證明了。 我寧願不同意， 實在不想豐富多彩的各種宇宙都終結於一條規則。

按照我們當下的知識， 我們存在的物理世界也是一個有邊界的世界。 與圍棋世界沒有根本上的不同。 下出來的棋， 就不能收回去，時間只有一個方向。 有邊界的棋局早晚會被填滿， 而物理世界終將歸於熱寂。 除非：

NP 不等於NP

其實還有不屬於NP的NP hard世界，那個世界完全不可理喻，我們不去玩兒。

謝謝觀賞！