Hacker News Reader

It's not even needed to introduce weird derivatives, a publicly traded company can announce $1,000,000 dollar prizes for factoring a RSA keys.

In fact, you can embed more powerful oracles like this, e.g. publicly traded company announces a $1,000,000 dollar prize for anyone who submits an inconsistent statement in ZFC.

The EMH is a framework. With any scrutiny it's obvious that it can at most be first order accurate since obtaining and processing information is costly. This is not a particularly new insight or one that would be a surprise to any proponent of the EMH.

The complexity of factoring RSA keys is not known, so this method isn’t sufficient.

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

> The EMH is a framework. With any scrutiny it's obvious that it can at most be first order accurate since obtaining and processing information is costly. This is not a particularly new insight or one that would be a surprise to any proponent of the EMH.

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.

>at most be first order accurate

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

When someone says a consideration is orthogonal to another one, they are not literally embedded in an Euclidean space. In this context, first order is used loosely to mean that the deviations come from effects which are only secondary in magnitude and relevance, not to indicate that we're looking at the asymptotic behavior of a formula when a parameter is taken to be infinitesimal.

The trouble is that EMH is a formula, so the "to first order" thing has a literal meaning that is not what the author meant. It's kind of like saying that "1-x^2/2 is cos(x) to first order," moreso than saying "my business plan is a good idea for every involved party, to first order."

>This is like saying “life is NP-hard.” Like, yeah, of course it is. That doesn’t mean we aren’t pretty good at doing the right thing and rationality (like EMH) is a good, if imperfect tool to analyze behavior.

The granularity of the "correctness" is the major difference here and you're asking the author to be ok with an extremely rough success criteria when they are proposing a mathematically perfect success criteria.

So, define how you would quantify "pretty good" in comparison with "mathematically optimal" and you might get what is in effect an infinite delta.

>but a basic model of rationality would say that humans can “perfectly” solve it.

"basic model of rationality" doesn't make sense. Rationalism has not been shown to provide a pathway to a general epistemology.

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.

> The granularity of the "correctness" is the major difference here and you're asking the author to be ok with an extremely rough success criteria when they are proposing a mathematically perfect success criteria.

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.

>"Nash-equilibria are PPAD-hard (and communication hard) so Nash-equilibrium as a concept is bad because it's computationally difficult."

I think that's a perfectly cromulent position actually. It's a great example where the theory doesn't help when you're working with real non-homo economicus agents, and I would argue hurts if you assume that people behave (or should) behave according to those concepts.

>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)

...even worse. Go find me one of these perfect information people. I suppose you could collapse the stated preference and revealed preference superposition into observed preference to solve the equation.

Sorry, I'm afraid I don't understand your position at all.

My point is that, like EMH, none of these are pretending to be the "be all end all solution to all models" and it's obviously silly to pretend otherwise? So it seems you're agreeing with me?

Maybe you and I agree that EMH shouldn't be considered god's truth, but macroeconomists who inform policymakers and asset pricing theory sure as hell do. Trust the market, market clearing etc... all come out of the philosophy.

I think that's the whole crux of the paper - the people informing how we structure our economy shouldn't consider EMH doctrine.

That only works if the alternatives to EMH are better heuristics than it is.

> Taking it to its extreme then everything breaks, because the model is wrong.

In my view it is a good thing to prove the model wrong, because so many people take extreme moral and political stances on account of the model being accurate.

At the very least, displaying counter-examples is a way to show those stances for what they are, exposing them as beliefs without scientific support.

> because so many people take extreme moral and political stances on account of the model being accurate

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.

>In my view it is a good thing to prove the model wrong, because so many people take extreme moral and political stances on account of the model being accurate.

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.

There have been (at least semi-)serious proposals that P=NP based on the fact that nature seems to be able to find optima to NP-hard optimization problems such as minimizing the area:volume ratio in a foam. Of course, they have been unable to give any reasonable arguments as to why those should be global optima.

Shameless plug for my Hiter parody of cranks who write such papers (modeled after Scott Aaronson's reaction to such a paper [0]).

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.

... visions of the NSA buying lots of washing-up liquid and old wire coat hangers.

Funny. Thanks!

Yeah, that rebuttal paper of Scott's was what I had in mind as well. And that Hitler parody was surprisingly funny, thanks :D

Glad to hear!

It's troubling to me to talk about "nature solving problems". Nature doesn't "solve" anything, those are meanings we humans assign to the various configurations of matter that we see, guided by our understanding of the underlying principles of motion (energy, fields, forces, or however you want to express them).

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.

Of course it's just a figure of speech. But it gets awkward to talk about, say, evolution, unless you can use anthropomorphic language at times. Even mathematicians discuss math using sloppy language all the time, only with the silent understanding that they could do everything rigorously if they really wanted to. Programmers anthropomorphize computers and software all the time. Does a sudoku solver not solve a problem just because it has no agency? Or is it different just because the human who wrote it does?

I think the distinction is important to address for the current discussion about P=NP, because of the meta nature of the discussion. Any argument about natural phenomena meaning anything a priori is obscuring the computation required ot assert meaning.

Proposals which don't survive contact with experiment. See pp. 3-4 of https://www.scottaaronson.com/papers/npcomplete.pdf

Doesn't that line of argument only work if nature's algorithms can be shown to be both precise (giving exact solutions) and complete (able to solve every valid problem)?

Yeah I doubt that nature is able to solve problems above a certain size. After you put together a certain number of soap bubbles they'll collapse into a black hole. Furthermore there are concerns of speed of light or speed of sound.

Nature might give efficient solvers for specific problems up to a certain size, but we already have "practical" NP problem solvers in classical silicon in the form of SMT solvers.

> we already have "practical" NP problem solvers in classical silicon in the form of SMT solvers.

They're out there, and practical for some problems, but SMT solvers aren't exactly a solved problem. They're used for deductive proofs about program correctness, which are still pretty finicky. [0]

[0] https://blog.adacore.com/using-spark-to-prove-255-bit-intege...

NP-complete problems can be polynomially reduced to each other. If you had a magical oracle that was able to solve any one specific NP-complete problem in O(1) time, you could turn that into a O(n^k) solution for all NP-complete problems.

That's the idea behind DNA-computing, for instance.

The question is whether it is actually possible to do so at a reasonable cost and at scale.

Regardless, what "nature" does has 0 to do with P vs NP, computability or anything else. P vs NP is a statement strictly about mathematical objects, there is no notion of "nature" anywhere in it.

Yeah, for sure. I mean, it's often the case (as I've found in my own research) that even relatively unsophisticated heuristics will often nail the global optimum for a good number of problems.

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!

> Here’s a silly one one: I give a derivative whose price is $1 if a solution (that is known to exist) to an NP-hard problem is found by a given time.

With a similar approach, we could 'prove' that market efficiency is non-computable, right?

"If you find me nth Busy Beaver program for any n>10, I'll give you $n"

I could be wrong, but that isn't known to be undecidable, is it? Merely extremely difficult?

I was thinking If you give me a program that solves the halting problem, I'll give you $1.

On reflection though, that's not just a bargain, it's also an outright contradiction; we know no such program exists, so making this offer doesn't affect the market at all. Perhaps there's a sneakier variation on this.

It is undecidable. If we had an algorithm to compute # of steps in Busy Beaver (n) (let's call it S(n)) then for all Turing Machines with n states run S(n) steps. If it doesn't halt, it will never halt. Halting problem solved! (well, blank tape halting problem, which is as hard as halting problem).

https://en.wikipedia.org/wiki/Busy_beaver#Proof_for_uncomput...

> On reflection though, that's not just a bargain, it's also an outright contradiction; we know no such program exists, so making this offer doesn't affect the market at all. Perhaps there's a sneakier variation on this.

We do know Busy beaver 1 to 4 (via brute force). We have lower bound for 5. It's definitely possible to compute more of these values. Uncomputable does not mean not possible to compute, it means you cannot find an algorithm that solves the problem in general.

So, maybe by dedicating bizarre amount of compute, you could find BB # 1M to claim your $1M from me. Get rich quick!

> This is like saying “life is NP-hard.” Like, yeah, of course it is. That doesn’t mean we aren’t pretty good at doing the right thing and rationality (like EMH) is a good, if imperfect tool to analyze behavior.

Most importantly, it doesn't mean that any alternative to markets are not also NP-hard.

> (a) we often don’t care about an exact solution

If we're trying to prove np-hardness we do.

It doesn’t really make sense in this case though, does it? One example is that Knapsack can be approximately solved in polynomial time for all tolerances eps (I.e., it has a Fully-polynomial time approximation scheme, or FPTAS). The EMH is only talking about essentially approximate behavior (as the paper also mentions, with repeated experiments).

Which is why this whole venture is more an exercise in pendantry rather than an actual attempt to solve np problems with markets.