Markets are efficient if and only if P = NP (2010)

Is it even theoretically possible to show that markets are efficient on purely theoretical grounds? As a thought experiment, imagine that all human brains have a weird defect that causes them to always ignore some specific kind of information when making pricing decisions, including when they write software dealing with those decisions, and under all other conceivable circumstances. In that case, it seems to me, it would be impossible to decide on purely theoretical grounds that markets are efficient because it strictly depends on the empirical observation that human brains have this weird defect. I could imagine the other way around to work, i.e. that there could be an obstruction to markets being efficient that can be shown to exist on purely theoretical grounds. But no matter what the answer to the second question is, in no case could you arrive at an »if and only if« result without including the empirical observation that brains do not have this weird defect.

First of all this paper leaves a lot to be desired in terms of rigor and it is for good reason not how mathematics is written by most mathematicians. It is very conversational and assumptions and derivations are jumbled together, while you sometimes find these in breakthrough papers from visionary mathematicians it often makes it harder to verify.

My understanding of the central argument in the paper is the following:

Definition: Let N be a positive integer denoting the length of the history, M be a positive integer denoting the number of assets. A market realization is an element of {-1, 1}^(NxM), i.e. M vectors of length n where all entries are either +1 or -1.

Definition: We call a function f: {-1, 1}^(TxM) -> {0, 1}^M satisfying f \circ s = s \circ f for s any element in the symmetric group S_M a technical strategy of lookback T. The symmetric group condition just states that permuting the vectors of length T among the M assets is the same as permuting the output the strategy. I.e. that the strategy has no inherent preferences among the assets.

The payoff of a technical strategy s on a market realization h is given by payoff(s, h) = \sum_{i=T}^N s(h_{i-T, ..., i-1}) \cdot h_i where the indexation is in the time dimension i.e. h_i denotes a length M vector. The budget of a technical strategy is budget(s) = max_{v \in {-1, 1}^TxM} s(v) \cdot (1, ..., 1). That is the maximal number of assets it wants to hold in any given state of the world.

Given a market realization h, positive integers B and K we say that h is (B, K) EMH-inconsistent if there exists a technical strategy s such that budget(s) = K. If a market realization h is not (B, K) EMH-inconsistent we call it (B, K) EMH-consistent.

Claim (presented as a theorem in the paper): The problem of determining whether a market realization is (B, K) EMH-consistent is in P if and only if the knapsack problem is in P.

Claim: The weak efficient market hypothesis is true if and only if EMH-consistency is in P.

In the second part of the paper he indicates a model of an order book where he wants to encode 3-SAT as combinations of market orders. I do not understand how this is intended to work, i.e. if all information is available and incorporated into the market and the information generating process is stopped, and I have bid-offer spreads because of transaction costs, and I irrationally (remember I am not interested in the buying or selling the security, I am just interested in solving a 3-SAT problem, thus my actions should not influence the price generation process of an efficient market) enter an OCO-3 order to buy A, B or C at mid. Why should this result in a transaction? In the case (a or a or a) and (!a or !a or !a) I make one trade with myself in the case (a or a or a) and (b or b or b) and (!a or b or b) I make one trade with myself, but one of the problems is satisfiable the other is not. Now it seems obvious that by inventing new order types we can get order book rules that allow for complex computation to resolve clearing, however this is a problem with the proposed order types not the efficient market hypothesis? A (to me) equivalent avenue of investigation would be to imagine different order types such that to decide the clearing of an order book it would involve solving an undecidable problem - i.e. what are the most reasonable order types and order book rules such that we can encode the halting problem?

On top of that, the argument rests on the kind of error you expect to see freshmen making in a discrete math course:

> The basic argument is as follows. For simplicity but without loss of generality, assume there are n past price changes, each of which is either UP (1) or DOWN (0). How many possible trading strategies are there? Suppose we allow a strategy to either be long, short, or neutral to the market. Then the list of all possible strategies includes the strategy which would have been always neutral, the ones that would have been always neutral but for the last day when it would have been either long or short, and so on. In other words, there are three possibilities for each of the n past price changes; there are 3n possible strategies.

There are 2^n possible histories of length n. If a strategy maps each history to one of three positions, there are 3^(2^n) strategies that consider n bits of history.

> "But given that there are 3n patterns to test, finding a solution, as opposed to verifying one, requires O(3^n), i.e. it is exponential in the size of n. For small n, this is computable, even though it is exponential. But as n grows, it becomes impossible to check every possible pattern quickly."

If a strategy is a sequence of BUY-HOLD-SELL decisions, then just because there's O(3^n) strategies doesn't mean you need to evaluate them all. It seems pretty easy (if a strategy is only defined in retrospect) to define a greedy algorithm that finds the optimal strategy. (see page 16.)

The author goes on to compare this to the Knapsack problem (pg 19). The thing that makes the Knapsack question (and NP-complete problems generally) hard is that greedy algorithms don't work (as far as we know), whereas it seems like a greedy algorithm work for the problem the author has laid out.

Why wouldn't it be 3^n? Edit: wait, it's because bitstring -> strategy is a function, right?