Is the market efficient? This is perhaps the most prevalent question in all of finance. While this paper does not aim to answer that question, it does frame it in an information-theoretic context. Mainly, Maymin shows that at least the weak form of the efficient market hypothesis (EMH) holds if and only if P = NP. 

First, he defines what efficient market means: 
"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, though of course any strategy could make money randomly."

For $n$ past historical price changes of {UP, DOWN}. Let there be three trading strategies that are neutral, long or short to the market. In order to check if there exists a strategy that statistically significantly makes money, requires checking all $3^n$ possible strategies. Verifying that a strategy is profitable beyond random chance can be done with a linear $O(n)$ pass of the historical data. Thus the problem of finding a profitable strategy is NP. 

If P=NP, then computing a profitable strategy can be done efficiently in polynomial time, since a trader can check each possible strategy in polynomial time. We can then trade based on our results to make the market efficient as well. If the market is efficient, it becomes impossible for a trader to predict future prices based on historical data, as the current price has all publicly available information "priced in". A future price would be a random fluctuation of the current price. 

Does an efficient market imply P=NP? 

An example 3-SAT:

$$(a \lor b \lor !c) \land (a \lor !b \lor d)$$

The NP problem of 3-sat can be encoded into the market using order-cancels-order (OCO) orders[^1]. 
Where each variable is a security and negated variables are sell orders. 

Place these two OCOs in the market.

$$\text{OCO (buy A, buy B, or sell C)}$$
$$\text{OCO (buy A, sell B, or buy D)}$$

After some constant time, any outstanding order is cancelled and all positions are liquidated. If the market is efficient, then there exists a way to execute these two OCO orders such that an overall profit is guaranteed. In other words, a market that is efficient allows us to solve an arbitrary 3-SAT problem in polynomial time. 

### **Takeaway**:
The author links market efficiency with computational complexity. 

[^1]: An order-cancels-order is a type of order on two different securities that automatically cancels the other order when one is filled. There is no chance that both orders can be filled.