logoalt Hacker News

skissane • today at 3:31 AM • 1 reply • view on HN

I think a proof of P=NP via a galactic algorithm is far more likely than a proof of P=NP via an efficient algorithm.

I mean if someone develops an O(n^100) algorithm for solving an NP-complete problem, that would prove P=NP, but pose no immediate threat to cryptography.

It increases risk, in that a galactic algorithm increases the odds that an efficient algorithm exists waiting to be found, but it is entirely (epistemically) possible that the galactic algorithm exists but the efficient algorithm doesn't.


Replies

fpoling • today at 5:32 AM

And vise versa, a proof that P!=NP do not exclude an algorithm that is fast enough for practical n.