Hacker News

points by skissane 3 days ago | 0 comments

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.

[–] fpoling 3 days ago

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

[–] Dylan16807 3 days ago

Maybe, but that feels significantly more exotic and unlikely to me. You have to basically negate the natural cost scaling of brute force in the thousand to million n range but lose that speed benefit later.

[–] skissane 2 days ago

Well, if someone found a quasipolynomial time algorithm – O(n^log(n)) – for an NP-complete problem, that would technically be compatible with P!=NP, but might have quite significant practical implications.

[–] Dylan16807 2 days ago

To have a really big impact you'd have to have that be the dominating factor at lower n and keep that "log(n)" part of the equation below 10 or so for all practical n. The latter one in particular seems unlikely to me.

[–] elfly 1 day ago

if someone finds a O(n^100) algo for NP complete problems, the obvious next step is to start lowering that 100 exponent.

Given the current developments, I would not be confident that it would not lower dramatically pretty soon.