5 ms·
"there's no bounds on the exponent for the runtime of an algorithm (O(n^100) is still in P), but this doesn't and hasn't happened in practice." That n^100 does
by dllthomas 11y ago
"there's no bounds on the exponent for the runtime of an algorithm (O(n^100) is still in P), but this doesn't and hasn't happened in practice."
That n^100 doesn't happen in practice might very well be selection bias. Perhaps humans are really bad at finding solutions that genuinely require polynomial work greater than O(n^4) [see note 1]. In fact, if P=NP, that would explain why we haven't thus-far found the polynomial time algorithms for any NP-complete problems.
"we would have to redefine what we mean by provable security, and then have to make some other arbitrary distinction. Is n^100 secure, but n^99 not?"
That doesn't seem materially different than having to pick key lengths. There is some amount of work you expect to be beyond what your opponents could theoretically muster. Pad a bit for safety.
"So for now P vs NP is an extremely useful distinction and I have yet to see a convincing argument that it's not."
We're using NP as a proxy for "provably different lower bound on checking versus finding". It's not a bad proxy, but having an actual proof of lower bound should be even better whether or not it is exponential, provided there's a sufficient gap to make realistic key sizes useful.
[1] Edited to add: As pointed out to me below, there are plenty of examples of O(n^k) with arbitrarily high k. This certainly undermines my speculation about human capabilities. At the same time, it means it does happen in practice.
- spooningtamarin 11y agoThere are plenty of algorithms with n^k where k>4, just not useful ones. Off the top of my head, checkout work by Eric D. Demaine. His work is on problems that seem very real, and solutions (algorithms) definitely show very lovely interaction of several different areas of research, problem solving skills at its finest. http://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant http://cstheory.stackexchange.com/questions/6660/polynomial-...
- dllthomas 11y agoThanks! That weakens my speculation about human capabilities, though the fact that it deserves calling out as "problem solving skills at its finest" seems to leave me some wiggle room ;) To be honest, I'm not sure how to quantify the relative populations of higher-exponent and lower-exponent found algorithms, and if there is a skew some of that might well be due to the decreased attention to the space of higher exponent algorithms due to lower expected usefulness...
- SilasX 11y agoIn cryptography, the goal is not to find problems that require O(n^k) steps to solve, but to find trapdoor one-way function families (the basis of public key cryptography) where the easy direction is O(n) and the hard direction (without the private key) is O(n^k) for arbitrarily high k. This would be easier to prove than O(exp(n)) and may even be quantum-computer resistant but I'm not sure if there are such cryptosystems, and if there are, they're not in common use since traditional models assume a polynomially strong adversary (as assumption we may want to relax).
- dllthomas 11y agoRight, relaxing the "it must grow faster than polynomial" might free up some new methods that we've foregone. But it's also the case that existing methods might still work fine - breaking them wouldn't be Omega(exp(n)), but may still have a high enough lower-bound for realistic values. Of course, if we discover that P=NP, getting at those lower bounds would be a priority...