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.