3 ms·

If P=NP then there is no encryption and no secure digital signature algorithms whatsoever. No post-quantum variants, I mean there's nothing at all. Also, if P=N

If P=NP then there is no encryption and no secure digital signature algorithms whatsoever. No post-quantum variants, I mean there's nothing at all. Also, if P=NP quantum computers are probably not useful at all, perhaps they're a bit cheaper, that's all. There's a lot of NP-hard problems that you'd love to solve if you could, but you avoid them because you immediately know it's not possible. For example, you could create optimal neural networks that might be 10x? 100x? more powerful for the same size/cost as GPT-4 is. This stuff is likely so beyond the reach of today's knowledge that it would be like talking about quantum mechanics and integrated circuits running at GHz speed to Euclides. It's like when Paul Erdős talked about the Collatz conjecture: "Mathematics may not be ready for such problems."

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.
yeeniee 3y ago
>If P=NP then there is no encryption and no secure digital signature algorithms whatsoever. I don't see how that follows. A polynomial can still have factors or constants on the orders of "not in this universe's lifetime", so for all practical purposes it doesn't matter.

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.

yeeniee 3y ago

>If P=NP then there is no encryption and no secure digital signature algorithms whatsoever. I don't see how that follows. A polynomial can still have factors or constants on the orders of "not in this universe's lifetime", so for all practical purposes it doesn't matter.