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

Great clarification. I'm always suspicious of interpretations of EMH that are a lot more literal than they should be, drawing effectively false conclusions from double negations. I think the truth is as you said.

The EMH is accurate to way better than the tangent line, which is what a first order approximation is.

It is known on a quantum computer factoring is polynomially hard.

As much as this is certainly the case (people using models wrong is one of my personal pet peeves), there are at least as many people who take equal and opposite extreme moral and political stances on account of the model being inaccurate.

Anyone who actually understand EMH just takes it for what it is.

> beliefs without scientific support

Any political or moral belief is a belief without scientific support. Those are simply not things within the domain of science. Anyone who says otherwise is just trying to bamboozle you into some weird ideology.

But this wouldn't affect thoses stances (in either direction). An EMH advocate can just (rightly) say, "Markets are efficient up to the limits of computation speed." Those same limits apply to anyone else's attempt to correct the market, so it doesn't validate view based on its negation either.

I mean, did nature "solve the problem" of creating human-like consciousness from inanimate matter? I suppose so, since humans are certainly human-like, and it would appear that there is a reasonable path from t=0 to now that includes building up all the structures at every scale to allow us to come enough into existence to talk about it with each other. But this way of speaking implies something that isn't there, namely an intention. Humans, to take one example, aren't a solution to a problem, we just are. And its the same for all interesting phenomena like, for example, the parabolic shape of a particle being thrown on Earth, or ball packing, or crystal lattices.... The fact that these structures are solutions to a problem is an artifact of the human ability to model the system mathematically in the first place. Nature doesn't model, she just is.

https://www.youtube.com/watch?v=NwUQVv7wCGA

[0] https://www.scottaaronson.com/papers/npcomplete.pdf

>> Last summer Bringsjord and Taylor posted a paper entitled “P=NP” to the arXiv. This paper argues that, since (1) finding a Steiner tree is NP-hard, (2) soap bubbles find a Steiner tree in polynomial time, (3) soap bubbles are classical objects, and (4) classical physics can be simulated by a Turing machine with polynomial slowdown, it follows that P=NP.

>> My immediate reaction was that the paper was a parody.

Here's one particular example: I tried what is essentially a greedy heuristic on a physical design problem (a problem where we design a device such that an excited wave within it best matches a specific shape). I had earlier showed that solving the general problem is NP-hard.

The objective value the greedy heuristic returned? .589. It took <100ms to compute this.

Now, I rewrote the problem in a way that was amenable to a mixed-integer convex problem solver (which involved some somewhat-complicated reductions because the problem isn't easily phrased in this way). Put it on Mosek (which is a pretty fast solver) and let it run.

The globally-certified optimal value (to <1%)? .587. Mosek took two and a half hours to find this.

So, tl;dr, the problem was "hard enough" that a branch-and-bound solver took a long time to solve, but still "easy enough" that a basic heuristic might as well have nailed the global optimum.

-----

I think the reason such papers keep popping up (and I see them around surprisingly often) is that people really don't realize how good basic heuristics really can be!

All I'm saying is that there are easier and clearer ways of presenting the same thing that could be done in a sentence and make the "reason why" obvious. No need to introduce gadgets and go on and on for 30 pages about "exponential time" (is the author talking about the exponential time hypothesis? Or is this P vs. NP?) among other things. There's also some additional crossed wires about "needing to try all cases" or something, that doesn't make any sense. No SAT solver/TSP solver/MILP solver, etc., does this. Anyone who is at all familiar with this topic would not make such statements, and certainly not, in the way you mention, a "mathematically perfect" criterion that "is proven wrong." So which is it? Is the author being cavalier about the literature? Or do they simply not understand the basics?

Additionally, they're not proving anything wrong. This is, like what I mentioned before, similar to bashing people for saying "Nash-equilibria are PPAD-hard (and communication hard) so Nash-equilibrium as a concept is bad because it's computationally difficult." (In fact, I'd say it's even less interesting than this, because at least the latter is a nontrivial result; not a one-line argument that we can embed arbitrarily complex things into the market.)

> Rationalism has not been shown to provide a pathway to a general epistemology.

This is "rational" as in "rational agent" (utility-maximizing, or an agent that makes at least Pareto-optimal choices, or who plays to Nash or correlated equilibria) not "rationalists" as in people who apply rationalism as an epistemology. Applied broadly, "rational agents" could solve halting-hard problems by making an obvious game where an agent who solves such a problem gets a million dollars, since such agents are often assumed to have unbounded computational power. (In particular, nothing about the agent's computational power is often assumed.)

> Fundamentally the author is making a really good case for the idea that oblique or poorly specified/constructed goal and measurement criteria (eg. EMH) should not be assumed as a competent goal vectoring mechanism for society.

Not really, no. For one, EMH says nothing about exact solutions (this would require a much more careful argument with a different type of reduction), and two, in the same way as before, putting EMH on a pedestal (like putting Nash equilibria on a pedestal, or agent rationality, etc.) leads to absurd results. My point is that (a) this is well-known and (b) you can make much simpler examples (like the ones above) that don't appear to be as "clever" but prove the same (nearly-obvious) point.

This is a particularly... interesting (for lack of a better word) submission to appear so repeatedly. Maybe it's just the right word-combination to appear in hn? Computer science + finance, with a touch of academic-ish?

Of course economists know that markets are not perfectly efficient, but what they tend to believe is that markets tend towards efficiency, and markets that are big enough and free enough will correct trivial inefficiencies relatively quickly.

This is why the advice is generally that returns in easy to access markets are very closely related to the risk you took on. If you made better than market returns, it's probably because (whether intentionally or not) you took on more risk than the market as a whole. This doesn't hold true for those with an information edge, but more people believe they have such a thing than actually have it.

Socialists need to discredit the market.

I doubt it is an “instruction” on markets efficiency — yes, if a government puts a lot of tax and newly-printed money in ponzi-schemes, bad things will happen.

"The efficient-market hypothesis (EMH) is a hypothesis in financial economics that states that asset prices reflect all available information."

2008 is not a contradiction and the other examples by the parent aren't contradictions either.

It's easy for politicians to blame 2008 on the markets, but I think it was caused by Keynesian government policies.

I assume we'll have similar problems soon with all the stimuli being granted.

It actually argues that if P=NP, and Moore's law continues indefinitely, then eventually someone could build an efficient market.

Were there free markets in the 17th century, would they have been able to incorporate Galileo's insight? Or would they have joined the church in denunciation? Part of me thinks that if they did eventually come around to the solar system, it wouldn't be all that quick.

In other words, you can also lose money, even if you're right.

1. Pseudo-Keynes: https://quoteinvestigator.com/2011/08/09/remain-solvent/

In order to make the EMH plausible, you have to restrict it so much that it's essentially meaningless: something on the order of, "If you take the ensemble of market players, they do not beat the market on average." But it's clear that individual market players do often better understand the value of particular assets than the market, and not just because they're lucky, but because they just do better analysis than the crowd does.

Similarly, the market can be 99.99% efficient, in which case it's obviously not entirely perfect but close enough that the average citizen is extremely unlikely to find any real arbitrages (which is what the EMH is essentially about).

IMO markets can't be efficient because we as humans aren't - our perception of value itself can be subjective and influenced by many things including FOMO, safety in numbers perceptions, risk aversion (usually), etc etc.

I love that meme for how wrong it is. Public companies don’t maximize short-term profits, maximize profits (with future profits discounted).

The fact that to a lot of people “profits” == “short term profits”, reveals quite a lot about our assumptions and time preferences..

Math, CS and Physics are the exception here.

Certainly, betting on nanosecond timescales seems very unlikely to be very beneficial for society at large.