“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. We can also program the market to solve NP-complete problems.” - Philip Maymin (Source)
Introduction
The efficient market hypothesis asserts that publicly available information should not permit persistent abnormal profits. In its weakest form, this means that past prices alone should not be sufficient to predict future prices profitably. Computational complexity introduces a parallel distinction. Problems in P can be solved in polynomial time. Problems in NP may be much harder to solve, but once a candidate solution is proposed, its correctness can be checked in polynomial time.
The key issue is not whether information exists, but whether it can be processed quickly enough to affect prices. Prior work on market efficiency often emphasized the impossibility of stronger forms of efficiency because information is costly to acquire and process. The present concern is narrower: even if one restricts attention to past prices, and even if that information is freely available, there remains a distinct computational burden in searching over all possible trading rules based on that data.
In short, while most refutations of market efficiency focuses on the cost of obtaining information, the present argument focuses on the cost of processing that information. We will first derive market efficiency from P = NP, and then derive P = NP from market efficiency, to show that the two are indeed equivalent.
The Information in Past Prices
Weak-form efficiency contains two claims that often run together. One is the “no free lunch” claim: once a profitable pattern becomes known and traders exploit it, the profit should disappear. The other is the “price is right” claim: any such pattern should be found immediately. We do not try to settle the first claim. Our target is the second. The market can only get prices “right” if all relevant patterns can be evaluated quickly enough.
Our initial heuristic model is deliberately simple. Suppose there are n past price changes, each coded as UP or DOWN. Suppose, further, that a strategy may be long, short, or neutral after each observation. Then there are 3^n possible strategies. Verifying a given strategy is easy: one linear pass through the data suffices.
So the decision problem lies in NP. But brute-force search appears to require checking exponentially many candidates. Even distributing the work across many investors does not change the basic asymptotic point: if P ≠ NP, the search burden eventually outruns total available computation.
Hence, as histories lengthen or become higher frequency, markets should become less efficient, not more (this accords with intuition that if markets are inefficient to technical signals, then those signals probably live in HFT domains). If P = NP, by contrast, a polynomial-time search exists, and markets can in principle eliminate all such opportunities.
However, the present notion of “strategy” is too loose. A sequence of ex post correct signals is not a genuine trading rule. So we formalize a technical strategy as
mapping a fixed lookback window of t binary price directions into a position: short, neutral, or long (we are indeed assuming a simplified binomial-tree world where things only go up or down). A long-or-out strategy is a restricted case that never shorts and outputs only 0 or +1.
The lookback window must be fixed. Otherwise a strategy could effectively encode hindsight by conditioning on the ever-growing entire history. In use, the input is applied on a sliding basis: first observations 1 through t, then2 through t+1, and so on. We note that the fixed-window condition is appropriate since many technical rules in practice, including momentum variants, already use fixed horizons.
This leads to the question: for a given lookback window t, does there exist a long-or-out technical strategy with statistically significant profit on a historical series of length n?
We note that this cannot be answered from the data alone. Statistical significance requires probabilities, probabilities require a null and an alternative, and that reintroduces the classic joint-hypothesis problem: any test of efficiency presupposes an equilibrium model of normal returns. However, all equilibrium and testing assumptions are compressed into a single critical profit threshold K.
In addition, there are in fact multiple securities for people to buy, and investors only have finite capital / margin. This leads naturally to the question
For a given lookback window t and a critical value of profit K (determined from given null and alternative models of market equilibrium) does there exist a long-or-out technical strategy S that generates a profit in excess of K on a collection of t-length vectors of zeros and ones such that the sum of the prices of the purchased assets does not exceed a budget constraint B?”
Compare the above question to the Knapsack Problem (Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible).
The price of a position plays the role of an item’s size s(u); the future return following a given subseries plays the role of value v(u); and the subset of subseries mapped to LONG is the chosen subset U′. The problem is to choose trades whose total size does not exceed budget B and whose total value is at least K.
Since knapsack is NP-complete, the existence of a budget-constrained profitable long-or-out strategy is polynomial-time solvable if and only if P = NP.
In other words, if P ≠ NP, the market cannot remain efficient for long because the relevant strategy space expands too quickly. If P = NP, the strategies can in principle be searched efficiently and traded away. That completes the first half of the equivalence: P = NP implies market efficiency.
Programming the Market
We now show that market efficiency implies P = NP. Assume weak-form efficiency holds for all n. Also assume that past publicly available information includes not only past prices but past public order histories.
Now, introduce the cross-security order-cancels-order instructions (orders on different securities that automatically cancel the remaining orders whenever one is hit), and not merely pairwise ones but orders spanning up to three securities. Call this OCO-3. Such functionality is not standard across distinct securities today, though it is not conceptually impossible.
The NP-complete problem chosen for encoding is boolean satisfiability, specifically 3-SAT (There are n teddy bears which are red on one side and blue on the other and there are m 3-armed aliens, each alien grabs 3 teddy bear hands, 3-SAT is the problem of determining if you can color the teddy bears such that every alien is holding at least one blue hand).
More technically, an expression built from variables, negated variables, ANDs, and ORs is satisfiable if some truth assignment of variables makes it true. 3-SAT is the restriction to conjunctive normal form with clauses of exactly three literals. Because 3-SAT is NP-complete, a polynomial-time procedure for it would yield polynomial-time solutions for all NP problems.
Now, each variable becomes a security. A positive literal becomes a buy order. A negated literal becomes a sell order. Each three-literal clause becomes one OCO-3 order. For example, the Boolean formula
is represented by two separate OCO-3 orders:
buy A, buy B, or sell C
buy A, sell B, or buy D.
The two OCO orders are separate, so execution in one clause does not cancel the other. Orders are submitted at minimum lot size and priced at the midpoint between bid and ask. The operational strategy is simply to submit all the orders, wait a constant amount of time, then cancel any unfilled orders and liquidate any positions.
If the market is truly efficient, and if there exists some pattern of executions across these OCO-3 orders that guarantees an overall profit, then the market ought to find it.
But such an execution pattern is exactly a satisfying assignment to the original 3-SAT instance. So an efficient market with OCO-3 functionality would be solving arbitrary 3-SAT problems in polynomial time. Since 3-SAT is NP-complete, that yields market efficiency implies P = NP.
Conclusion
To say that weak-form efficiency cannot hold unless P = NP is not to say that regulation can outperform markets, or that computational limits create an obvious role for intervention. It says something more precise and, in a way, more beautiful: the ideal of market efficiency is inseparable from the feasibility of computation itself.
That is what makes the argument so striking. Two questions that ordinarily live in separate intellectual worlds turn out to share the same structure. One asks whether prices can fully and rapidly absorb the information contained in the past. The other asks whether every efficiently verifiable problem is also efficiently solvable.
The connection is not rhetorical. It is exact. If markets truly extract and incorporate all the implications of past prices, then they must be accomplishing something as difficult as solving NP problems efficiently. And if NP problems can be solved efficiently, then the exhaustive search over technical strategies that weak-form efficiency requires becomes possible in principle.
Market efficiency is not merely an informational claim. It is a computational claim. Past prices do not become informative simply by being public. They become informative only when their implications can actually be found, verified, and acted upon before the opportunity disappears. The theorem exposes that hidden requirement with unusual clarity.
It also sharpens the meaning of inefficiency. An anomaly need not imply irrationality, institutional failure, or a defect calling for correction from outside the market. It may instead reflect a more fundamental fact: the search space generated by financial data is combinatorially vast, and the market, however sophisticated, is still bounded by the same computational limits that constrain every other information-processing system.
Disclaimer
The information provided on TheLogbook (the “Substack”) is strictly for informational and educational purposes only and should not be considered as investment or financial advice. The author is not a licensed financial advisor or tax professional and is not offering any professional services through this Substack. Investing in financial markets involves substantial risk, including possible loss of principal. Past performance is not indicative of future results. The author makes no representations or warranties about the completeness, accuracy, reliability, suitability, or availability of the information provided.
This Substack may contain links to external websites not affiliated with the author, and the accuracy of information on these sites is not guaranteed. Nothing contained in this Substack constitutes a solicitation, recommendation, endorsement, or offer to buy or sell any securities or other financial instruments. Always seek the advice of a qualified financial advisor before making any investment decisions.