Remix.run Logo
BoardsOfCanada 2 hours ago

A lot of things are only true if P != NP but says nothing about P being within epsilon of NP.

jfengel 2 hours ago | parent [-]

Not quite sure what you're suggesting here; perhaps it's satire?

If P!=NP then it is arbitrarily smaller, for the same reason that e^x > Cx^N for any constants C and N, as long as x grows big enough. There is no epsilon in that can overcome that, no matter how big you make it, because x will eventually dominate the equation.

There are a lot of cases where pragmatically x remains small enough that it doesn't matter, and a P algorithm will give you an answer more quickly. (For the same reason I only ever write bubble sorts: I would only write my own at all if I knew that the list would never be bigger than 10. Even then it's only when using the library is too much trouble for some reason.)

But we care about P and NP when the number can potentially be very, very large.

BoardsOfCanada 40 minutes ago | parent | next [-]

No, it's not satire. The difficulty of finding the optimal solution says nothing about what it takes to come within 99.999% of optimal with 99.999% probability.

So I'm not talking about the number of steps needed to prove optimality with a correct P algorithm versus an exponential one.

I'm only talking about how this applies to the efficient market hypothesis.

IsTom 2 hours ago | parent | prev [-]

In case P /= NP the gap doesn't necessarily have to be exponential, just superpolynomial (e.g. n^loglogn).