I prove that 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 "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.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
Hi! I am a person who reads crankery.
First, thank you for self-assessment. It's rare.
This paper constructively suggests that P=NP iff EMH: https://arxiv.org/abs/1002.2284
It may be worth reading up on PPAD and Nash's thoughts on P=NP.
Do not despair, but do not expect to be correct, either. Explore and be wrong, but look for proofs, too. Above all, do not forget that crankery is fundamentally about being unwilling to see existing proofs and results. Always try to open your mind.
Thanks for the considered response.
> "Markets are efficient if and only if P = NP": https://arxiv.org/abs/1002.2284
That's a very cute result, but requires a very specific definition of 'efficient market'. There's actually a range of 'efficient market' definitions, each with their own 'efficient market hypothesis'.
One of the weaker forms that I like is: 'don't expect to make any money trading stocks as an amateur on news that the full time professionals (and their computers) in the hedge funds and at Goldman have already seen.' (This one is mostly useful for internet discussions with people who believe in reading price charts etc.)
The paper basically shows that if you…
Read the full comment
want to be really careful in your definition of '(weakly) efficient market', you need to take computational complexity into account. It says more about definitions, than about the economy. In any case, if you like that kind of thing, you should check out https://scottaaronson.blog/?p=735 too.
---
> In this case, government control makes this sector function as a planned economy. The normal flaw in a planned economy is that it cannot respond quickly to changing consumer demand, and I do not dispute this.
There's lots more wrong with (most) planned economies.
Eg the demand for toilet paper is---covid aside---famously easy to predict. Yet, the Soviet Union was also infamous for their toilet paper shortages.
> In the case of medical issues, consumer demand is a lot more predictable by the government than by the general public, as the demand 20 years from now is mostly directly influenced by other government interventions in the meantime [...]
The government officials in power today are most likely not the government officials in power over the next 20 years. In most cases, it's not even the same party that's in power. Current government officials don't necessarily have any special insight into long term government actions.
> No. Where do you get that misinformation?
> Yes, it's relatively easy to construct a model where perfect information and a bunch of other assumption lead to markets being great. But that merely shows that these conditions are sufficient. Not that they are necessary.
"Markets are efficient if and only if P = NP": https://arxiv.org/abs/1002.2284
To quote:
"""
I prove that 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…
Read the full comment
“program” the market to solve NP-complete problems. Since P probably does not equal NP, markets are probably not efficient.
"""
> Non sequitur? Reminds me of the famous syllogism https://en.wikipedia.org/wiki/Politician's_syllogism
I think I see what you mean, as I didn't give sufficient justification.
In this case, government control makes this sector function as a planned economy. The normal flaw in a planned economy is that it cannot respond quickly to changing consumer demand, and I do not dispute this.
In the case of medical issues, consumer demand is a lot more predictable by the government than by the general public, as the demand 20 years from now is mostly directly influenced by other government interventions in the meantime (governments have a better awareness than random 18 year olds choosing their university degree of the plausibility of a smoking ban or a sugar tax, they can change pollution rules to ban leaded fuel, etc.), and the exceptions are things like "novel global pandemic" or "we're at war now" where the government has to directly intervene in other ways anyway.
If markets were perfectly efficient there would be no entrepreneurs.
To start a business of any kind is to hypothesize the existence of a market inefficiency, something the market is not currently doing that would make it more efficient. All business is in some sense arbitrage between state A, the market as it currently exists, and state B, the market with your business in it. A business succeeds if its hypothesis is correct and if it executes well.
Also there's this: https://arxiv.org/abs/1002.2284
The Efficient-market Hypothesis has been proven to be true only if P=NP.
https://arxiv.org/abs/1002.2284
What's your bet on the latter? I'm... skeptical.
> The stock market provides an efficient medium for the allocation of capital.
Only if P=NP.[1]
Besides
Efficiency: the ratio of the useful work performed by a machine or in a process to the total energy expended or heat taken in.
This also begs the question: "To efficiently allocate capital (energy) for what goal (work)?"
And it doesn't look like the answer to that is "the betterment of humanity", but to push the bell curve of wealth as far to the left as possible with the longest tail possible, externalities be damned.
The stock market isn't a usefull tool for society like kickstarter, but a wealth extraction mechanism for the wealthiest.
So I'd argue that HFT isn't any more immoral than T.
1: https://arxiv.org/abs/1002.2284
Weak form efficiency - https://arxiv.org/abs/1002.2284 is one such proof.
For strong form efficiency (which requires markets perfectly reflect all available information) -
You would have trouble finding people who still believe in strong form efficiency.
The weak form paper above cites several papers that go into why strong form efficiency is impossible. There are formal proof versions around. In practice, even empirical studies of strong form efficiency haven't supported it either - it's just very easy to find practical counterexamples.
I never said that central planning must work better or worse, just that Hayek's reasoning doesn't hold up because it starts from the ridiculous assumption that markets always find the equilibrium, always propagate local knowledge, etc.., and those are the reason why they theoretically are better than planning according to Hayek. I'm arguing against a purely theoretical argument that was cited with purely theoretical reasoning. The source for Hayek's assumptions implying P=NP is this : https://arxiv.org/pdf/1002.2284
I personally don't care for the purely theoretical arguments that Hayek makes, and yes the arguments are full of apriorisms and assumptions but that's the…
Read the full comment
Austrian school for you and that's what you need to prove that markets must be better than planning.
The actual argument I'd make why planning can outperform markets in many industries and cases is pretty straightforward - markets require duplication of labour, they cause intrinsic crashes, they hurt knowledge transfer because they require intellectual property, they require infinite growth, and more.
Meanwhile actual implementations of planning have been plagued by incredibly slow iteration times (in the order of 5-4 years), access to data so horrible that CIA data was sought by planners, excessive centralization due to the impossibility of getting popular input, very low transparency, limitations in processing as data was collected and processed by hand, allocation of resources by hand, etc...
Planning is fundamentally a computer science problem at every level, and every single major defect can be fixed or palliated using techniques developped from computer science.
Because of this and the relative competitiveness, on the order of 1/3, of planning despite horribly deficient implementations, I think that there's a solid shot that planning can be a better solution than markets in most cases, though not all.
Finally, central planning doesn't actually mean eliminating markets - they are still useful for gaging the relative value and demand in consumer goods. Rather, the goal is to replace capital markets.
There, that's my case for why it is very probable that planning can be a better alternative to capitalist markets in most cases.
I don't know if you are a Computing Scientist, but you might find this parallel interesting: "Markets are efficient if and only if P = NP"
https://arxiv.org/abs/1002.2284
Well, a naive, overly strong formulation of the efficient markets hypothesis may imply that P=NP. Something like "an optimal trading strategy is a function depending on the entire market history, and in order to find an optimal trading strategy, one must check an exponentially large space of such functions."
The paper is here: https://arxiv.org/pdf/1002.2284.pdf. They do a sketchy reduction to an extremely stylized model of the market from the knapsack problem and 3-SAT.
This is unsurprising. P likely is not equivalent to NP [0], and predicting the market is NP-hard [1]. It's nice to see empirical work in the field, though, and especially nice to see reproductions of published papers.
[0] https://www.scottaaronson.com/papers/pnp.pdf
[1] https://arxiv.org/abs/1002.2284
Edit for downvoters and repliers: If enough market participants are irrational, then it can still be possible for people to predict other people, instead of the market, and make money that way.
NP-hardness indeed doesn't rule out heuristic approaches, but experience with 3-SAT and other NP-complete problems suggest that there will be arbitrarily bad times, and that in those times, the amount of loss can be exponential in the length of time that the heuristic poorly predicts the market.
> efficient markets are not deceptive markets. Participants are assumed to share equal information.
Unfortunately this does not exist outside the textbook; there's an entire field devoted to information economics (Akerloff, Stiglitz et al). And then there's the brilliant "markets are efficient iff P=NP" paper: https://arxiv.org/pdf/1002.2284.pdf
Even an efficient market will still have capital be more expensive for goods people disapprove of and aren't willing to support. An efficient market just means the price is discovered, not that the price solely reflects monetary outcomes.
Plus there's probably no such thing as an efficient market; determining future outcomes of a market is an NP-complete problem and there are finite traders, so unless P equals NP you are definitely on the moral hook for the impact of your investment decisions. https://arxiv.org/pdf/1002.2284.pdf
(edited for source)
There is no such thing as a free market: it is an idealistic theoretical construct.
And even if it were real, it would only be efficient if P=NP[0].
0. http://arxiv.org/abs/1002.2284
It would be a boon for laissez-faire capitalism, as it would prove that markets are at least weak-form efficient.
Reference: http://arxiv.org/abs/1002.2284
> Efficient markets have already priced in all these well known reasons for one.
Too bad there's no such thing as an efficient market [1].
[1] http://arxiv.org/abs/1002.2284
> one where you can comfortably afford living, fun, saving, etc I think is most people's interpretations
My understanding is that most people's understanding of "middle class" is "about 20% richer than me", and that this remains true regardless of how rich one is.
Most people, for most of the years since Joseph Marie Jacquard realised he could control a loom with punched cards, the Red Queen race of automation has given us more stuff and experiences per hour of labour — if you wanted to live the 1820s idea of a middle class life, you can retire as soon as you get around €$£ 25-50k of savings (just don't start a family, the rest of society considers this standard to be…
Read the full comment
unacceptable for that, what with no electricity).
If this improvement in living standards is despite, or because of, each business trying to maximise revenue, is basically the entire disagreement between Adam Smith and Karl Marx; though it's worth also noting that neither liked rent-seeking, and if you have a completely efficient market then nobody can extract any profits because competition drives margins to zero… but also since then we've had research show that complex markets aren't and can't be efficient: https://arxiv.org/abs/1002.2284
I think that's a pretty valid question to ask, but one that doesn't sit right with the typical neo-liberal/venture-capital clientele on HN.
The wishful image of financial autonomy and chances of personal and business development through a public market seems to provide too much cognitive dissonance when confronted with the realities of how bloated, speculative, manipulated, and self-fulfilling stock markets have become.
It's like telling someone who's put their entire live saving into bitcoin that it's a pyramid scheme.
I mean any other idea would probably die on here, once it's been shown that it's success is coupled to NP=P being true.(https://arxiv.org/abs/1002.2284)
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
The author presents two tricks to accelerate depth-first search algorithms for a class of combinatorial puzzle problems, such as tiling a tray by a fixed set of polyominoes.
Jon Kleinberg, Sendhil Mullainathan, Manish Raghavan
Recent discussion in the public sphere about algorithmic classification has involved tension between competing notions of what it means for a probabilistic classification to be fair to different groups.