3 ms·
> If P=NP then there is no encryption and no secure digital signature algorithms whatsoever. Why do you say that? A problem being in P does not necessarily me
by enriquto 3y ago
> If P=NP then there is no encryption and no secure digital signature algorithms whatsoever.
Why do you say that? A problem being in P does not necessarily mean that it's easy, or that it is solvable at all in practice. Recall that the class P contains problems that require a running time of O(n^A(6,6)), where A is the Ackerman function. This is an inconceivably large number, and there's no realistic expectation to solve such a problem for even minuscule values of n, like n=2 or 3.
The class P is huge, and our puny linear and quadratic algorithms can only solve its lower, trivial levels. We have not yet started scratching the surface of the enormous set P, yet some of us are arrogant enough to call all of it "easy".
For all we know, it may well be that P=NP but have no practical consequences whatsoever.