NP 問題就這樣解決了!?

P .vs. NP 是計算機科學一個很重要的未解問題，等級為 P 的問題是能在多項式時間內解決的問題，NP 問題則是能在多項式時間驗證解答是否正確的問題，顯然 P 問題是 NP 問題的子集，但 P 是否等於 NP，一直無法證明，也無法推翻。

財務領域也有個很重要的有效市場假說（efficient market hypothesis），在有效市場裡，市場價格已經充分反應所有證卷市場的歷史訊息，所以分析過去的資料以預測市場未來走向是行不通的。

這兩個問題似乎是八杆子打不着關係，但是有位牛人（Phil Maymin）嘗試證明這兩個問題是等價的，他投到 arxiv 的論文說他能夠證明如果市場是弱式有效市場（weak-form efficient market），那麼 P = NP，反之亦然。到目前為止，這篇文章我只讀了三頁，我想就算通篇讀完，以我的程度也無法判斷這位牛人說的究竟有沒有道理。若有高人能現身釋疑，小弟感激不盡。總之，我的感想，這位多才多藝的牛人，實在是太牛了。

這篇文章應該要歸檔至 to_read_later 類別，只是 later 究竟是多久以後，我也不知道？

Markets are efficient if and only if P = NP

Abstract: I prove that if markets are weak-form efficient, meaning current prices fully reflect all information available in past prices, then P = NP, meaning every computational problem whose solution can be verified in polynomial time can also be solved in polynomial time. I also prove the converse by showing how we can "program" the market to solve NP-complete problems. Since P probably does not equal NP, markets are probably not efficient. Specifically, markets become increasingly inefficient as the time series lengthens or becomes more frequent. An illustration by way of partitioning the excess returns to momentum strategies based on data availability confirms this prediction.

Creative Approach 有什麼不同 (2) - 談談數學歸納法

之前我曾談過， Udi Manber 寫作的演算法書籍 Introduction to Algorithms: Creative Approach花了一整章介紹數學歸納法，作者設計這本書的思路，是很值得思索和品味的。

歸納還是演繹

首先我們要搞清楚，數學歸納法，不是哲學上所講的歸納推理（ inductive reasoning） ，反而比較接近哲學領域所講的演繹 （deduction）推理。所謂的歸納推理，是基於對特定目標觀察的結果，把「性質」或「關係」類推至類型，或者是基於對反覆現象的觀察，所推理出來的規律或公式。歸納推理的結論只是有較大的機率為真，但不代表一定為真。

而演繹推理則是從已知事實為前提，必然得出的結論，如果前提為真，則結論必然為真。數學歸納法是基於一組已知的前提，推演出一個必然為真的結論，所以這個證明方法的精神是 deductive reasosing ，不是 inductive reasoning。

數學歸納法的基本敘述

Udi Manber 在他的書裡第二章末，參考文獻與進階讀物一節裡提到，數學歸納法是由 Francesco Maurolico 所發展出來的，事實上，數學歸納法的基礎可以上溯至更早的希臘時代的歐幾里德（Euclid），維基百科可以找到數學歸納法的歷史介紹，簡明扼要但資料豐富，有意者可自行深入研究。

最常見的數學歸納法敘述，是說一個關於自然數的命題 P，當這個命題符合以下兩個條件時，則這個命題對自然數恆真：

• P(0) 成立 (有的情況是講P（1）)
• 當 P(n) 成立，則 P(n+1) 也成立

或者我們用英文的敘述（對於看不慣中文翻譯的人來說，用符號和英文反而更親切，不是嗎？）：

• The basis: P(0) is true.
• The inductive step: If p(n) holds, then P( n + 1) holds too.

換句話說，當上面兩個條件成立，P(n) is true for all natual numbers 。

用矛盾法（contradiction）證明數學歸納法的正確性

從高中到大學，我們學習數學歸納法，都是被動的背誦數學歸納法的證明手法，鮮少在課堂上探討歸數學納法可以證明命題敘述對在自然數這個集合裡一定是正確的。其實我們可以用矛盾（又稱歸謬證明法 - Proof by contradiction）法來驗證證明這個方法的正確性。

我們的前提如下：

1. P(0)
2. For all n ≥ 0, P(n) ⇒ P(n + 1)

然後我們現在要證明對所有大於零的自然數，P 這個命題恆真，就是
For all m ≥ 0, P(m) is true ...................................... （3）

接下來就是證明的核心，假設 （3）是錯誤的，那我們一定可以找到一個最小的數 m' 使得 P(m') 不成立，我們現在要證明這個假設是有衝突的，所以 （3） 不可能是錯的，（3）必須是真的。

首先， m' 不可能是 0，因為前提 （1） 已經告訴我們 P(0)必須成立，所以這個 m' 如果存在，一定大於 0。當我們找到這個所謂的 m' ，我們知道前提 P（m' - 1） 是成立的，因為 m' 是最小的令命題 P 不成立的數字，但是前提（2）告訴我們，P(m'-1+1)=P(m) 這個敘述必必須為真。這和我們的假設是衝突的，所以不可能找到令 （3）不成立的數字m'。換言之，P（x）這個敘述對於所有自然數都成立，我們已經證明數學歸納法在前提確立的狀況下，是打不破的。

皮阿諾公設(Peano's Axioms)

用今日數學的術語來說，數學歸納法就是皮阿諾公設(Peano's Axioms)中的第五公設。所謂公設（或稱公理 axiom），就是在某些學門中不需要證明，但卻必須被承認的敘述或命題，有的書籍翻譯為公理。公理是一門學問的基礎，這門學科的所有理論、定理，必然可以由這些最基礎的公理推演而來，如果基礎不被承認，這門學科也就無從存在，公設的重要性由此可見。

義大利數學家 Giuseppe Peano (皮阿諾) 在 1889 年以拉丁文寫作一本小冊子 Arithmetices principia, nova methodo exposita ( The principles of arithmetic, presented by a new method )，這本書將自然數的性質抽象化得到一組公設。希望藉著這組公設，透過邏輯的推演，可以演繹出自然數的所有性質。 皮阿諾把每一個自然數的下一個稱為這數的「後繼者」(successor)，用後繼者的說法， 這組皮阿諾公設可以寫成下面的形式（括弧裡是用符號的寫法，其中 n+ 表示自然數 n 的後繼者）:

1. 0是一個自然數。
2. 若x是一個自然數，則另有一個自然數X'(緊隨X之後)。X'稱為X的直接繼數。
3. 0不是任何數的後繼者
4. 對任何自然數X與y，若X'=Y'，則X=Y。
5. [歸納原理]若P是一個性質(Property)，並且(i)0其有性質P；(ii)若任何自然數X具有性質P：則X'具有性質P，則所有自然數其有性質P。

數學歸納法不同的面貌

標準的數學歸納法證明，可以分為三個部分

• The Base Case (in the domino analogy, this shows the first domino will fall)
• The Induction Hypothesis (in the domino analogy, we assume that a particular domino will fall)
• The Inductive Step (in the domino analogy, we prove that the domino we assume will fall will cause the next domino to fall)

只要遵循以上三部曲的建構方式，通常都能順利找到證明的思路，發展出 induction step 來證明所欲證明的標的。事實上，在作數學歸納法證明時，有許多技巧上的變化，比如說：

☆（１）先證明ｎ＝１，ｎ＝２時命題成立；

　（２）假設ｎ＝ｋ－１，ｎ＝ｋ－２的時候命題成立

　（３）證明在此情形下，ｎ＝ｋ時命題也成立。

或者像這樣

☆（１）先證明ｎ＝１到ｍ時命題成立；

　（２）假設ｎ＝ｋ的時候命題成立

　（３）證明在此情形下，ｎ＝ｋ＋ｍ時命題也成立。

數學歸納法，並不是只有一個面貌，經過長久的發展，數學歸納法已經發展出許多的變異模式，適用於不同的場合與目的，甚至有些數學家開發出將數學歸納法延伸至自然數以外領域的模型出來。以最精簡的符號來表達，我們一般常見的數學歸納法的變化形式可能包括以下幾種情形：

Standard Formulation

• The basis: P(0) is true.
• Induction hypothesis: assume P(n=m) holds.
• The inductive step: If p(m) holds, show that P( m + 1) holds too.

Strong Induction

• The basis: P(0) is true.
• Induction hypothesis: assume for all n <= m, P(n) holds.
• The inductive step: If p(n) holds, show that P( n + 1) holds too.

Reverse Induction

• P(M) is true for some M
• If P(n=k+1) holds, show that the property holds for n = k.

依照上述證明方式，我們得到結論： The property holds for all values n <= M

Transfinite Induction

Transfinite induction 一般而言是應用在 well-ordered set 上，通常只有真正念數學的人，才會關心這個咚咚吧？ 根據 PlanetMath 的說明， Transfinite induction 的定義如下：

證明的陷阱，切記！切記！

前輩數學家華羅庚曾經講過一個故事 ：一位買主買了一隻公雞回家。第一天，餵公雞一把米；第二天，又餵公雞一把米；第三天，還是餵公雞一把米。連續十天，每天都餵給公雞一把米。公雞就這十天的經驗，下了一個結論說：每天一定有一把米可吃。但是就在得出這個結論後不久，家裏來了一位客人，公雞就被宰殺成為盤中飧請客人了(這個故事可以在昌爸工作坊找到)。

有人建議把數學歸納法想像成骨牌效應（falling dominos ），一張骨牌倒下來，下一張骨牌接著倒下去，就這麼一張一張倒下去，用遠不會停。問題就在這邊，我們必須確認一張骨牌一定接著一張，才能確保數學歸納法的正確與適用。

換句話說， P(n) 成立，不代表 P(n+1) 一定成立，千萬不要認為理所當然，我們的任務是確認 P(n) ⇒ P(n + 1)，不是默認 P(n) ⇒ P(n + 1)。

為什麼寫

原本只是打算在複習演算法時，順手記錄看書時的想法，但是在唸書時，看到第二章，在回顧自己學習數學歸納法的過程時，冒出許多想法，所以就順手把找到的東西發展出一篇完整的東西。

Creative Approach 有什麼不同

為了準備資格考，在圖書館借了 Introduction to Algorithms: A Creative Approach 的中譯本（沒法子，找不到原版），實驗室的同學翻了翻，覺得這本書一點兒都不出奇，和別的演算法書籍沒有什麼不同，尤其和這些年被奉為聖經的 CLRS 演算法大磚頭相比，相形下有點單薄了。

的確，中文書名建構式演算法，實在不怎麼響亮，而且在建構式數學已經被污名化的今日，這樣的書名實在是讓人很難不看低這本書。

但是在我的眼裡，這本書不同的地方可多著咧。

首先，作者的來頭不一般，這本書的作者 Udi Manber 可不是蛋頭型的學者，他不僅在學術上的成就卓著，是演算法界大師級的學者，他還是一個活力十足的行動派。 Udi Manber 是agrep 和 GLIMPSE 的（共同）作者。agrep 是他和吳昇(他的著作)老師在九零年代初共同發展的，他們共同寫作的 Agrep - A Fast Approximate Pattern-Matching Tool，依照 Google Scholar 的搜尋結果，被引用次數達到 143 次，以一篇年紀這麼大的文章，被引用次數達到這個程度，是很不容易的。簡單說，他是搜尋引擎相關技術演算法的先驅者之一。

離開學界，進入產業界，他也是一條過江猛龍。1998 年，他加入雅虎，職位是 chief scientist ；2002 年，他加入亞瑪遜網路書店，擔任 chief algorithms officer，這個 CAO 職位，還引起 IT 媒體界一陣騷動，紛紛評論這個職位對於企業的意義和影響(impact)。在 Amazon 期間，他還是搜尋引擎 A9 的 CEO。後來，毫不令人意外地，他在 2006 年加入了 Google ，擔任工程部門的副總裁（之一），當我在媒體上看到 Google Snatches A9 Chief 的新聞標題， 心裡不由得覺得又是這樣，有股淡淡的憂傷在心頭走過。

其次，另外一個特別的地方是，這本書用了整整一章的篇幅，介紹數學歸納法（mathematical induction）。數學歸納法是一個非常重要的證明技法，這個方法衝破思考的侷限，將思考的限制從有限，推展到無限的領域。思考範圍的突破，是數學歸納法很重要的貢獻，而且掌握數學歸納法的證明形式與技法，對於掌握邏輯推演的技巧，也有不小的貢獻。

很可惜，國內除了數學科系之外，鮮少在課堂上針對數學歸納法，作深刻透徹的說明，所以許多學習數學歸納法的學生，很難真正理解這個證明技法在學習上的意義，更別談從這裡發展出「作」證明題的一套適合個人的思路。

所以，這本書的寫作思路，和其它的演算法書籍，的確是不同的。接下來，我想應該花點時間整理數學歸納法了吧（待續，stay tuned ...）。