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

While this is a fun, the title is a little strong.<p>There are three limitations (whuch apply to many papers about P=NP).<p>1. The market could still be efficient, because the situations which must arise to cause P vs NP problems are very complicated. In particular thry require very expensive indivisible things to buy, whereas in most situations we can treat things like shares as continuous with only a small error.<p>2. Markets could be efficient if P=NP and we know how to solve NP probkems in P, and we do it. The title makes it sound like the market will already be efficient if P=NP, which isnt true.<p>3. Even if P=NP, the polynomial could still be big enough the market cant be efficient. Similarly, P could not equal NP but the expoenential be small enough markets can still be efficient in reality.

Most people seem to read this as a proof that markets are inherently flawed and as lending support to their ideological distrust of market economies. I think that if the authors thesis holds true and p indeed != np, this kind of conclusion could spell an even bigger problem for those who advocate to agument or replace market economies with another, typically more centralized, form of economic calculation. Allende&#x27;s cybersyn famously used linear programming (P) in order to centrally &#x27;simulate&#x27; and improve upon more regular market mechanics. If the authors thesis holds I think it&#x27;s actually an argument in favor of the economic calculation problem talking point of Hayek and the like: efficient calculation of economic distribution problems is impossible and flawed dynamics of the market are probably close to the best approximation we can afford.

I&#x27;m amazed that someone has written a paper that considers computational complexity that isn&#x27;t written in LaTeX...

Frankly, everybody with a bit of economic common sense knows that efficient market hypothesis (EMH) is just a weird theoretical nonsense which is nowhere close to describing real world.<p>If you want a full critique, read Steve Keen&#x27;s Debunking Economics, it has a chapter on EMH.<p>Oh and by the way, there is quite a bit of people who believe that P=NP. Most famously Donald Knuth. I recently became convinced about that as well.<p>Amusingly enough, the first thing that a rational person would do upon discovering a relatively efficient algorithm to solve NP problems would be to cash in all the Bitcoins. Thus proving in practice that no, markets are not really efficient. :-)

What does this mean for the class of PPAD-complete [1] problems?<p>Someone correct me if I&#x27;m wrong, but if 1. Nash Equilibrium ⊂ FNP 2. &quot;Markets are efficient&quot; =&gt; FNP ⊂ FP<p>How is this different from &quot;FP = FNP if and only if P = NP&quot; [2], which is a result already found?<p>[1] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;PPAD_(complexity)" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;PPAD_(complexity)</a> [2] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;FNP_(complexity)" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;FNP_(complexity)</a>

&gt; &quot;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.&quot;<p>If a strategy is a sequence of BUY-HOLD-SELL decisions, then just because there&#x27;s O(3^n) strategies doesn&#x27;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.)<p>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&#x27;t work (as far as we know), whereas it seems like a greedy algorithm work for the problem the author has laid out.

This paper is rubbish. Trading is ultimately a partial information, sequential game with an unknown number of participants whose payoff functions (and utilities) are also unknown. Could the market be closer to being efficient if P=NP? Likely. Does P=NP imply efficiency? Not at all.

Interesting topic and thought experiment. But this theory is not very fleshed out and not at all convincing (especially the part regarding using an existing efficient market to perform computation for anything other than price of the underlying instrument, i.e. what the computation is intended for). The following quote sums up how the author makes very open ended assumptions:<p>&gt; So what should the market do? If it is truly efficient, and there exists some way to execute all of those separate OCO orders in such a way that an overall profit is guaranteed, including taking into account the larger transactions costs from executing more orders, then the market, by its assumed efficiency, ought to be able to find a way to do so. In other words, the market allows us to compute in polynomial time the solution to an arbitrary 3-SAT problem.<p>In reality, most financial markets are pretty efficient but none are perfectly efficient -- if they were perfectly efficient, it would imply not only perfectly efficient trading systems and an inability to get an &#x27;edge&#x27; on the market, but also perfectly efficient market systems, which are limited by technology, conventions, and regulations (for example, significant inefficiencies arise in US securities from not being open all the time, with very little liquidity still available in the &#x27;after hours&#x27; markets). To achieve even &#x27;pretty good&#x27; efficiency requires significant energy, and I&#x27;m not sure I understand how the author can imply that the energy used in the past to calculate the current price is equivalent to the energy to verify the current price. As a trader, I can tell you that most market participants do not care to verify past calculations of the current price; they only care about the future price, and will generate an action from the differential between the predicted price and the current price.

I have always been puzzled by why we as computer scientists give such importance to P vs NP. I always thought that even if P = NP the solutions might still be much harder (but only polynomially) to find than to verify. I always get angry when people say that P = NP would mean that problems would be equally as easy to solve as to verify. So, because of that, P v NP always seemed irrelevant to me.<p>But in the article, there is an interesting section on that:<p>&gt; If P = NP, even with a high exponent on the polynomial, that means that checking strategies from the past becomes only polynomially harder as time passes and data is aggregated. But so long as the combined computational power of financial market participants continues to grow exponentially, either through population growth or technological advances, then there will always come a time when all past strategies can be quickly backtested by the then-prevailing amount of computational power. In short, so long as P = NP, the markets will ultimately be efficient, regardless of how high the exponent on the polynomial is; the only question is when, and the answer depends on the available computational power.<p>So this section, if I understand it correctly, says that problems in P are easy because the computational power in the world grows exponentially and we can assume that they will at least once become feasible to solve.<p>That&#x27;s an interesting way of looking at it. Is this really the reason why we consider polynomial problems much easier than NP-hard ones?

Before people get too carried away criticising markets, check this quote from the paper.<p>&gt; The results of this paper should not be interpreted as support for government intervention into the market; on the contrary, the fact that market efficiency and computational efficiency are linked suggests that government should no more intervene in the market or regulate market participants than it should intervene in computations or regulate computer algorithms.

The market cannot be efficient because a large portion of public information is not true.<p>Even if all the information was true, there is still the problem that humans have very poor reasoning abilities combined with herd mentality which almost always overrides the reasoning part.<p>To predict the market, you don&#x27;t need to understand the market, you need to understand people&#x27;s distorted view of the market.

I don&#x27;t think anybody would claim that even the weak form of the EMH applies in all cases. Like the idea that objects of different weights fall at the same speed it&#x27;s an approximation that can be very close to true in some cases but can be badly misleading in others. If you&#x27;ve ever listened to economists talk about prediction markets they always seem to bring up the idea that markets with low capitalization have low efficiency.<p>And even looking at the highly capitalized stock market I know at least one story of a major player that got its start noticing a violation of weak-form efficiency and becoming very rich by fixing the violation.<p>There&#x27;s no reason to think that actual markets are now finally efficient and in fact there are some that are publicly know, but which only bring a small return and require decades of investment to fix so nobody is interested in trying.

Based on a quick skim, this is not a good paper. Computer scientists writing on economics is great, it&#x27;s helpful to grow new ideas in the field. Unfortunately they sometimes use economic concepts imprecisely at detriment to their question, methodology, and results.<p>That&#x27;s the case here. This paper posits a definition of efficiency, but does not explain why that definition is correct or how it relates to other efficiency measures.<p>A better proof of arbitrage opportunities in markets is Wah 2016, which identifies actual arbitrage opportunities in actual markets.<p>Separately, what does &quot;Since P probably does not equal NP&quot; mean as a probabilistic statement?<p>And what is the correct way to concisely and precisely write: &quot;most people familiar with the P = NP problem believe with varying degrees of confidence that P is not equal to NP, but so far no proof exists.&quot;

As I understand it, his argument is that there might be information available that needs time to interpret. And that the time the market took to interpret the available data is not sufficient to gain the maximum insight possible. So that somebody with more computing power then the market could beat the market.<p>I don&#x27;t see that as an argument against the EMH. I think it is inherent in the EMH that the market has more computing power then any individual.<p>I would say that it is the core of the EMH. That more people make better predictions. Because they have more computing power.<p>I always found it strange that the EMH is often defined as the market price including all available data. As if the data can simply be added without interpretation.

So just to better understand the issue of P=NP, am I right in assuming that an NP problem is like trying to build a neural net for image recognition?<p>In the sense that it takes a huge amount of time and images to train the thing to become smart (in other words, to go through the entire network of neurons one by one and assign better weight values etc) but when it comes to actually verifying if our network is smart all it takes is to run an image straight through the network?<p>And the issue of trying to prove N=NP is essentially trying to prove that there isn&#x27;t a magical way to train a neural network with just one image of training data?

Reading this comment thread is hilarious to a degree. I think that it really highlights how much noise gets thrown into a discussion when your naming becomes too relatable. Essentially bike shedding of theory discussion. If the Efficient Market Hypothesis has been called the “Fundamental Market Property Hypothesis M = H” or similar I doubt most would have made the comments they made. But because “efficient market” sounds to relatable most feel that they can comment without even knowing what the specifics of the EMH are.

Meh. Whatever your opinions on P = NP, the efficient markets hypothesis is unfalsifiable. You can only falsify a joint hypothesis of efficiency plus some model of information flow into a market.

The author’s claim only applies to weak form of market efficiency.<p>The original Fama paper distinguishes between three forms of the EMH: weak, semi strong and strong.<p>The weak form only alleges that historical price info is fully incorporated in the current price. You can still make money by working hard and figuring things out from outside the price history.<p>The weak form applies to purely technical trading that extracts value from price history like momentum and the simple moving averages cross over studies you see.

<a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Information_asymmetry" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Information_asymmetry</a> is still rampant e.g <a href="https:&#x2F;&#x2F;www.economist.com&#x2F;books-and-arts&#x2F;2018&#x2F;06&#x2F;02&#x2F;the-rise-and-fall-of-elizabeth-holmes-silicon-valleys-startup-queen" rel="nofollow">https:&#x2F;&#x2F;www.economist.com&#x2F;books-and-arts&#x2F;2018&#x2F;06&#x2F;02&#x2F;the-rise...</a>

Interesting. It is well known in the high-frequency literature that at frequencies higher than 5-minute one obtains market microstructure noise. The observations you observe do not fully reflect the &quot;true&quot; price. I.e. you observe bid&#x2F;ask quotes with a spread and the &quot;true&quot; price is somewhere in between. This is due to the bid-ask bounce and other latency factors. How can markets ever be efficient if we can not observe the true price of something?

P = NP when you nail it.<p>From the paper: &quot;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 &quot;program&quot; the market to solve NP-complete problems.<p>However, there has been no proof that there does not exist some algorithm that can determine satisfiability in polynomial time. If such an algorithm were found, then we would have that P = NP. If a proof is discovered that no such algorithm exists, then we would have that P ≠ NP. Just as most people in the field of finance believe markets are at least weak-form efficient, most computer scientists believe P ≠ NP. Gasarch (2002) reports that of 100 respondents to his poll of various theorists who are “people whose opinions can be taken seriously,” the majority thought the ultimate resolution to the question would be that P ≠ NP; only 9 percent thought the ultimate resolution would be that P = NP. The majority of financial academics believe in weak form efficiency and the majority of computer scientists believe that P ≠ NP. The result of this paper is that they cannot both be right: either P = NP and the markets are weakly efficient, or P ≠ NP and the markets are not weakly efficient. &quot;

What kind of markets get created when the input to the NP problem is 2^10000, I think our idea of markets are based on small scale transactions and extrapolations can&#x27;t take into account intelligent agents. Also Arrow&#x27;s theorem hints how small formals systems can&#x27;t achieve agents desires. Anyway, I have only read the title not the arxig paper.

Can&#x27;t markets just assume that it is and move on. It&#x27;s not like markets never do speculation &#x2F;s

Somehow this seems to be a confusion of categories: markets are real-world mechanisms, while P and NP are mathematical abstractions. Does not compute. To the extent that it does, it&#x27;s typical mathematical macroeconomic BS.

Does this also mean if we can prove that markets are efficient then P = NP?

Even if P ist not equal NP, hardness of efficient markets could be in APX2 i.e. computing a solution that is at most twice as bad as the optimal solution is in P.

Er, markets are massively parallel, yes?<p>Um, am I wrong in thinking that P and NP refer to non-parallel algorithms?<p>(Apologies in advance if I&#x27;m having a brain fart.)

Profit is the measure of inefficiency in a market.

free market efficiency is an evolutionary concept not accounting one. there&#x27;s no intelligent design.

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.<p>My understanding of the central argument in the paper is the following:<p>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.<p>Definition: We call a function f: {-1, 1}^(TxM) -&gt; {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.<p>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.<p>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) &lt;= B and payoff(s, h) &gt;= K. If a market realization h is not (B, K) EMH-inconsistent we call it (B, K) EMH-consistent.<p>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.<p>Claim: The weak efficient market hypothesis is true if and only if EMH-consistency is in P.<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?

Therefore it&#x27;s false.

That&#x27;s why we need peer-review.

The title of this post scores 10000 HN points.

But markets are not efficient ...

Efficient or not efficient, as long as it can make me rich, I&#x27;m OK with it.

&quot;For simplicity but without loss of generality, assume there are n past price changes, each of which is either UP (1) or DOWN (0).&quot;<p>You know, this is the kind of thing that makes me wonder about how much quantum computation is going to change the game.<p>Where we aren&#x27;t just calculating ups and downs but superpositions between the two.

Have another account here but don&#x27;t want to take the karma hit for being a crank. I published this 2-page proof that the EMH is false:<p><a href="https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1011.0423" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1011.0423</a><p>(didn&#x27;t set the date so in the document it&#x27;s wrong, this was published 2010.)<p>It doesn&#x27;t depend on P = NP, it&#x27;s simply a rigorous proof that EMH is false.<p>Let&#x27;s switch gears a second. Here&#x27;s a famous elementary proof[1] that there are infinite primes. Suppose there are just finite primes, up to some largest. Multiply them together and add one. No prime divides the new number (because &quot;every&quot; prime leaves a remainder 1), so you&#x27;ve just produced a new prime. This new prime is larger than the largest prime in your finite set because you multiplied that by the rest of them and added one to get it. So this is a contradiction, you couldn&#x27;t have had finite primes up to some largest.<p>Anyway if you think there might be a largest prime after what you just read, it just means you don&#x27;t understand the proof. If you believe EMH might be true it just means you don&#x27;t understand the proof that it is false.<p>Of course, nobody ever even hypothesized that academia was efficient :)<p>[1] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Euclid%27s_theorem#Euclid&#x27;s_proof" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Euclid%27s_theorem#Euclid&#x27;s_pr...</a><p>--<p>EDIT: no mistake in my comment