upvote

points

by slashtrends6 hours ago |
comments
upvoteby sampo5 hours ago|
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)

reply
upvoteby steezeburger4 hours ago|
parent|
prev|
[-]
That premise is great.
reply
upvoteby devy6 hours ago|
prev|
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.

reply
upvoteby Someone54 seconds ago|
parent|
next
[-]
[delayed]
reply
upvoteby hathawsh5 hours ago|
parent|
prev|
[-]
Or it could indicate that more resources have been put into cryptography than most other math fields, so AI hasn't yet caught up to our progress.
reply
upvoteby murderfs3 hours ago|
parent|
[-]
It seems rather unlikely that solving the Navier-Stokes problem is harder than e.g. a better attack on a reduced-round AES. Perhaps they think an epsilon improvement in the exponent isn't worth publishing, but it seems more likely that they're intentionally withholding any results they have.
reply
upvoteby treebeard9012 hours ago|
parent|
next
[-]
It's a reasonable assumption that the cases where the NSA, etc, had a role in designing cryptographic systems, and reportedly made specific suggestions that could be forms of a backdoor, would all be revealed by AI being tasked to find it. Maybe even indirectly as part of the broader defensive security research by models unreleased to the public. If algorithmic complexity or a really obscure backdoor has existed in cryptographic systems and put there by the Gov't, it seems that current frontier models would have the best chance of revealing it.
reply
upvoteby Maxion2 hours ago|
parent|
prev|
[-]
Either that or they've not put the model(s) on those problems. Remember that even the Navier-Stokes solution did use a large amount of compute. I'm not sure they'd even want to waste it on problems that they can't get PR from.
reply
upvoteby skissane5 hours ago|
prev|
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.

reply
upvoteby fpoling3 hours ago|
parent|
[-]
And vise versa, a proof that P!=NP do not exclude an algorithm that is fast enough for practical n.
reply
upvoteby Dylan168071 hours 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.
reply
upvoteby mattm5 hours ago|
prev|
[-]
The 2012 movie "Travelling Salesman" is a thought provoking film that explores this scenario.
reply