alt Hacker NewsPart of the problem with the current centralization of the world's math capability within AI labs is that if they do find that P=NP via an efficient algorithm, it could have implications on all modern public key based cryptography. So it's not completely clear that they will (be allowed to) release these results.
Replies
> if AI frontier labs do find that P=NP via an efficient algorithm, it could have implications on all modern public key based cryptography.
The fact that other math problems are bulk solved yet nothing from cryptography was released/published as solved could be a strong indicator that "all modern public key based cryptography" could have been at risk.
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.
The 2012 movie "Travelling Salesman" is a thought provoking film that explores this scenario.
> it could have implications on all modern public key based cryptography
Here's a nice low-budget scifi movie about this:
https://en.wikipedia.org/wiki/Travelling_Salesman_(2012_film...
https://www.youtube.com/watch?v=OgeyHkP6i3g (full movie)