According to Phillip Maymin of the NYU Poly Department of Finance and Risk Engineering:
Markets are Efficient if and Only if P = NP
Abstract:
I prove that if markets are 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.
I guess this means that libertarians will be petitioning the Clay institute to collect their million dollars then?
Oh boy! What a fine post! It sure gives a person to think, what is this discipline that folks call “financial engineering?” No other comment, save Ave pontificis! 🙂
Of course centralized planning is also at least NP-hard 🙂
You can encode halting-problem hard problems into a market (eg. this derivative pays “risk-free interest-rate plus one dollars” when this Turing machine halts), hence the claim is false (an NP oracle cannot solve the decision problem).
This post overlapped substantially with topics on Gödel’s Lost Letter and on Shtetl Optimized; after consideration I posted merged reflections on Gödel’s Lost Letter … with a back-link to Quantum Pontiff … which means other folks will be coming here, in hope of reading snappy comments from the QIT community.
“I also prove the converse by showing how we can “program†the market to solve NP-complete problems.”
Is there any reason he has to stop there? Seems like he can “program” the market to solve problems in any complexity class. All he’s doing is creating a situation where the incentive consists of solving a problem from the class in question.
Maybe this is all an instance of the greater “fallacy” that demand creates supply.
Recently, Scott A. answered difficult questions so efficiently that there can be no longer any doubt that P=NP.
I was discussing this with a quant friend of mine, and I think I came up with a good analogy. The Efficient Market Hypothesis (EMH) is like the idea in ‘classical’ physics that, as you cool atoms down further and further, they move less and less, until they stop moving and you reach absolute zero. This paper comes along and says, “If the Heisenberg uncertainty priciple is true, then absolute zero doesn’t exist!” It’s attention grabbing, sure. But it shouldn’t be too surprising that a general principle, taken to extremes, runs up against a technical limitation from a more rigorous yet wacky field. It’s a definitions problem, which doesn’t mean that it’s not a useful concept or that you can’t cool things to pico-Kelvins.
The paper states “the weakest form of the EMH states that future prices cannot be predicted by analyzing prices from the past. Therefore, technical analysis cannot work in the long run.” I hope most people would reject the idea that no form of technical analysis works in the current, real market. (Such analysis pays my paycheck, after all.) So, the real market is not EMH efficient, but perhaps we believe its approaching that asymptote, ie, “in the long run”. What this paper says is that, if P!=NP (as most CS people believe), then it’s *computationally* impossible for a market to actually reach the EMH asymptote, and the contrapositive, if it *were* ever possible for markets to reach true EMH efficiency, then P==NP. However, the paper does not suggest that markets don’t trend toward the EMH asymptote. There are some pretty darn good 3SAT and Traveling Salesman solvers out there too.
Personally I think it just means things are more interesting than we thought and there’s more research to be done. 🙂