というタイトルの論文（原題は「Markets are efficient if and only if P = NP」）が少し前のMarginal Revolutionで紹介されていた*1。ただしエントリのURLは「just-dont-claim-i-said-this-was-true」となっており、取り上げたタイラー・コーエン自身は、論文が正しいと裏付けしたわけではないよ、と但し書きを付けた格好になっている。
以下にコーエンが引用した要旨を紹介しておく。
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.
（拙訳）
本論文では、市場がウィーク・フォーム効率的、すなわち現在の価格が過去の価格において利用可能な情報をすべて反映している、ならば、P=NP、すなわち多項式時間内に解が検証可能な計算問題はすべて多項式時間内に解くことが可能であること、を証明した。また、NP完全問題を解くように市場を「プログラム」する方法を示すことにより、その逆も証明した。PとNPはおそらく等しくないので、市場はおそらく効率的ではない。特に、時系列の期間が長くなるか、頻度が高くなるにつれ、市場はより一層非効率的になる。モメンタム戦略に対する超過収益率をデータの利用可能性に基づいて分割するという例示により、この予想が正しいことが確かめられた。
なお、この論文を書いたのはPhilip MayminというNYU–Polytechnic Instituteの准教授だが、このコーエンのエントリのコメント欄に降臨して、その前のコメンターに反応すると同時に、（コーエンが紹介したリンクとは別の）SSRNのリンクを書き込んでいる。
*1:ちなみにNP問題関連としては、昨年10月20日の拙ブログでもファイナンスに絡めた論文を紹介したことがあった。
