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 2 hours ago | parent [-]

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

	▲	Dylan16807 12 minutes ago \| parent [-]
		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.