Comment by Animats
12 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.
Linear programming admits a worst-case polynomial time algorithm.
It is notable that simplex, especially dual simplex is often better in practice, especially for integer linear programming with branch and bound because you only have to slightly modify the parent optimal basis in simplex vs entirely restarting or refactorizing for interior point methods.
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.
> In cryptography, most of the problems believed to be exponentially hard, such as factoring, don't have proofs of an exponential lower bound.
Actually, integer factorization already has subexponential-time algorithms, such as the General Number Field Sieve (GNFS).
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?
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
ETH has no impact on most of cryptography, as it was never based on NP-hardness in the first place.