Hacker News

points by Animats 3 days ago | 0 comments

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.

[–] vlovich123 3 days ago

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)

[–] robryk 2 days ago

> 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.

[–] svat 3 days ago

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.

[–] luma 2 days ago

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.

[–] tomaskafka 2 days ago

Just like when the Manhattan project could be recognized by all the nuclear scientists stopping publishing.

[–] w4der 2 days ago

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?

[–] Animats 3 days ago

Not by this result. But it opens up a new area of problems to hammer on that might get somewhere.

[–] marcus_holmes 2 days ago

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...

[–] FlyingCanoe 3 days ago

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

[–] m-chrzan 2 days ago

Given the context, Animats probably was speaking of integer linear progamming, which is NP-complete.

[–] caughtinthought 2 days ago

And interior point is regularly outperformed by an exponential time algorithm (simplex) lol

[–] LPisGood 2 days ago

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.

[–] wslh 2 days ago

> 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).

[–] williamstein 2 days ago

> In cryptography, most of the problems believed to be exponentially hard, such as factoring, don't have proofs of an exponential lower bound.

There are subexponential algorithms for integer factorization, e.g., the general number field sieve and Lenstra’s ECM.

[–] marcosdumay 2 days ago

With about O(2^(n/log(n)) instead, I imagine those people are deeply interested on the impacts, but nobody will be losing their sleep.

[–] Ar-Curunir 2 days ago

ETH has no impact on most of cryptography, as it was never based on NP-hardness in the first place.