Hacker News new | past | comments | ask | show | jobs | submit
slashtrends | on: The Exponential Time Hypothesis Is False [pdf]
Part 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.
sampo | parent | next
> 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)

loading story #50254923
loading story #50254739
devy | parent | next
> 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.

loading story #50254379
skissane | parent | next
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.

loading story #50255038
mattm | parent
The 2012 movie "Travelling Salesman" is a thought provoking film that explores this scenario.