3 ms·
A lot of things are only true if P != NP but says nothing about P being within epsilon of NP.
by BoardsOfCanada 3mo ago
A lot of things are only true if P != NP but says nothing about P being within epsilon of NP.
- jfengel 3mo agoNot 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.
- IsTom 3mo agoIn case P /= NP the gap doesn't necessarily have to be exponential, just superpolynomial (e.g. n^loglogn).
- BoardsOfCanada 3mo agoNo, 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.