| ▲ | slashtrends 5 hours ago |
| 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 3 hours ago | 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) |
| |
|
| ▲ | devy 5 hours ago | parent | 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. |
| |
| ▲ | hathawsh 4 hours ago | parent [-] | | 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. | | |
| ▲ | murderfs 2 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. | | |
| ▲ | treebeard901 37 minutes 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. | |
| ▲ | Maxion 37 minutes 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. |
|
|
|
|
| ▲ | skissane 4 hours ago | parent | 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. |
| |
| ▲ | 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 11 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. |
|
|
|
| ▲ | mattm 3 hours ago | parent | prev [-] |
| The 2012 movie "Travelling Salesman" is a thought provoking film that explores this scenario. |
