5 ms·
"P vs NP is not really that important because n^1000 might as well be NP" And yet P seems to capture pretty well the concept of "problems for which there are e
by dgordon 18y ago
"P vs NP is not really that important because n^1000 might as well be NP"
And yet P seems to capture pretty well the concept of "problems for which there are efficient algorithms." For whatever reason, no algorithm seems to have a complexity like O(n^1000). I don't know why. I'm not sure anyone does. But the highest exponent I can think of right now is n^12 for the original upper bound on the AKS primality testing algorithm, and I think that was later reduced to n^6.
- Retric 18y agoOk n^1000 was a little over the top but how far you can scale is still outside the question of P vs NP. N^2 means 10 million is not acceptable in a reasonable amount of time. (10^14) N^6 hit's 10^14 at 216. N^log N hit's 10^14 a little after 5500 [edit 5517] and it takes 1,000,001 before it's worse than N^6 but it's all downhill from there.
- dgordon 18y agoWhat are the units? 10^14 is indeed far too much if it's seconds, but might not be beyond reason for a set of size 10 million if it's nanoseconds (then you have a bit under three hours.) So think about which units this would actually have. Indeed, an algorithm being in P may not be sufficient to scale, but if a problem is NP-complete (assuming P != NP) there's almost certainly no scalable algorithm for it.
- Retric 18y ago(10^14) nanoseconds = 1.1574 days I should have said If N^2 means 10 million... Anyway, I tend to think of 10^10 nanoseconds as vary bad (10 seconds) and (10^14) > 1 day as unreasonable, but that's just a rule of thumb from the days of 1Ghz CPUS's.