Comment by Animats
9 hours ago
There are hard problems where the worst case may be exponentially hard, but the average case is much faster. Linear programming and the traveling salesman problem are like that. The faster approaches are considered "probabilistic solutions".
In cryptography, most of the problems believed to be exponentially hard, such as factoring, don't have proofs of an exponential lower bound. There's some risk of a breakthrough that makes those problems easier. A probabilistic solution would be good enough to break many cryptosystems.
I suspect that people at the cryptanalysis agencies worldwide are staying up late tonight, trying to figure out the impacts and risks of this new result.
Funny you mention probabilistic algorithms. If I’m not mistaken one of the OpenAI results is that most of the probabilistic methods (specifically those that use a logarithmic amount of space)-4 have non-probabilistic versions that are as efficient in time and space (L = RL = BPL)
> most of the probabilistic methods (specifically those that use a logarithmic amount of space)
These are by far not most, nor most of the practically useful ones. Directed graph reachability, given an adjacency list as input, is NL-hard.
For linear programing, the interior point method has a polynomial worst case.
It also not probabilistic, so linear programing is not rely a good example
Given the context, Animats probably was speaking of integer linear progamming, which is NP-complete.
And interior point is regularly outperformed by an exponential time algorithm (simplex) lol
Incidentally, Ryan Williams says (https://x.com/rrwilliams/status/2114891838377320784):
> In fact, one of the first things I wanted OpenAI to check is that no existing cryptosystems are compromised by the result. Apparently they are safe...
so if you trust his trust of OpenAI, then this has no (immediately obvious) bearing on cryptosystems for now.
Not by this result. But it opens up a new area of problems to hammer on that might get somewhere.
Seeing the panicked state of the PHP ecosystem at the moment, and having worked in the financial system in the past, I dread the thought of what would happen to global banking if a frontier model broke a maths problem that underpins our crypto systems...
Somehow, their wide range of results touch every single area of math except anything touching cryptography. I think it's fair to expect that three letter agencies are given the ability to veto the publication of certain discoveries.
Just like when the Manhattan project could be recognized by all the nuclear scientists stopping publishing.
Wasn't there a comment a while ago when all major LLM providers went down almost at the same time that it was caused by a sort of virtual "Room 641A" thing?
ETH has no impact on most of cryptography, as it was never based on NP-hardness in the first place.