| ▲ | jfengel 2 hours ago | |
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). | ||