Hacker News new | ask | show | jobs
by BoardsOfCanada 25 days ago
A lot of things are only true if P != NP but says nothing about P being within epsilon of NP.
1 comments

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.

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.

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