Hacker News

points by svat 3 days ago | 0 comments

While this has no immediate bearing on P-vs-NP, it is interesting to note:

- Early CS researchers like Donald Knuth entered CS in the days when regularly someone would come up with a surprising faster algorithm for some problem, and their intuitions were that most problems had faster algorithms than you'd expect.

- Later generations of CS researchers, as all the easy algorithms were discovered, and post Karp's definition of NP-completeness (and the Garey & Johnson book, say), began to specialize in proving hardness, and complexity theory with a “zoo” of complexity classes became more about separation and lower bounds, e.g. I've seen algorithms like Arora's PTAS for Euclidean TSP being described as a “failed attempt to prove a lower bound”. So an entire generation of researchers' intuition was mostly in the direction of an elegant universe with neat separation results (even if we couldn't get them).

- So e.g. surveys of computer scientists showed most of them believing that P≠NP, and someone like Knuth has always seemed a bit of an outlier for saying that maybe P=NP: his argument was simply that there are so many possible polynomial-time algorithms that we haven't explored, and maybe one of them with a large exponent could solve NP-complete problems. (In response to arguments that many researchers have failed to find any such algorithms, he would say that many researchers have failed to prove that P≠NP.) E.g. in 2017 when Scott Aaronson wrote his survey (https://www.scottaaronson.com/papers/pnp.pdf = https://www.scottaaronson.com/papers/pnp-kindle.pdf) he wrote:

> Admittedly, it can be hard to tell whether declarations that P = NP are meant seriously, or are merely attempts to be contrarian. However, we can surely agree with Knuth and Lipton that we’re far from understanding the limits of efficient computation, and that there are further surprises in store.

- What we've seen in this month is surprising unexpected algorithms, like o(n log n) algorithms for FFT and integer multiplication, and now this sub–exponential-time algorithm for 3-SAT. (Yes the ETH has had less support than P≠NP but I still gather it's unexpected.)

So (though I don't expect intuitions on P≠NP to change, and probably that's still the right intuition… but I'm just an interested amateur), maybe there will be a bit of a swing of the pendulum back to the idea that maybe clever algorithms exist that we just haven't thought of.

[–] Animats 3 days 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.

[–] 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.

[–] slashtrends 3 days 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.

[–] devy 3 days ago

> 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 3 days ago

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.

[–] freehorse 2 days ago

Also most of the results come from "spray attacks". In addition to the results that are found there are also tons of failed attempts on other problems. So merely through how large the whole space is one should not necessarily expect groundbreaking results in cryptography specifically (even though it can also be true that some results be withheld, at the same time).

[–] murderfs 3 days ago

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.

[–] bscphil 2 days ago

Maybe I'm misunderstanding you, but a better attack on a reduced-round AES has been achieved by LLMs. Anthropic did it and published it already, a chosen plaintext attack that improves on state of the art against reduced-round by "200-800x". https://anthropic.com/document/aes_mobius_bridge.pdf

[–] treebeard901 3 days ago

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 3 days ago

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.

[–] Someone 2 days ago

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

“Could be”, but I think the correct way to describe it is “the general public doesn’t know”. It could be any of

- they tried very hard without finding weak spots

- they tried for a while, and gave up because the LLMs didn’t even produce leads

- they tried, found something and kept it for themselves

I think the first is not unlikely. Before LLMs, the likes of the NSA must have looked really hard into these problems, and IMO it’s not likely they found something substantial (if they did, their counterpoints in other large countries likely would find it, too, and some of them would have used that knowledge)

[–] orangecat 2 days ago

"They've specifically avoided trying" is also a possibility. Because what do they do if they actually find a critical flaw? Publishing leads to mass chaos. If they don't publish but it leaks, also mass chaos. (Probably just leaking the existence is enough without the actual proof). If they're "responsible" and report it to NSA, there's a good chance that model development gets forcibly halted and some chance that the entire company gets seized on national security grounds.

[–] freehorse 2 days ago

The issue is that if a country's agencies find an efficient attack to modern public key based cryptography with LLMs, there is no reason to think that other countries will not find the same in a few months with their LLMs. So, finding a vulnerability could offer a short term advantage, but one would want eventually to protect their own, too.

[–] sampo 3 days ago

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

[–] kenjackson 2 days ago

This is also the premise of Sneakers. I don’t think they prove P=NP, but it’s inferred they find fast factoring (although never explicitly).

[–] yablak 2 days ago

Also "Silicon Valley"

[–] bananaflag 3 days ago

This is a book about this:

https://www.goodreads.com/book/show/37986693-factor-man

[–] steezeburger 3 days ago

That premise is great.

[–] skissane 3 days ago

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 3 days ago

And vise versa, a proof that P!=NP do not exclude an algorithm that is fast enough for practical n.

[–] Dylan16807 3 days ago

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.

[–] skissane 2 days ago

Well, if someone found a quasipolynomial time algorithm – O(n^log(n)) – for an NP-complete problem, that would technically be compatible with P!=NP, but might have quite significant practical implications.

[–] Dylan16807 2 days ago

To have a really big impact you'd have to have that be the dominating factor at lower n and keep that "log(n)" part of the equation below 10 or so for all practical n. The latter one in particular seems unlikely to me.

[–] elfly 1 day ago

if someone finds a O(n^100) algo for NP complete problems, the obvious next step is to start lowering that 100 exponent.

Given the current developments, I would not be confident that it would not lower dramatically pretty soon.

[–] mattm 3 days ago

The 2012 movie "Travelling Salesman" is a thought provoking film that explores this scenario.

[–] dingdongditchme 3 days ago

I believe this stems from an incomplete understanding of the problem space on my part (excuse the multiple puns); but, I am skeptical Knuth really said P=NP. There are so many mathemtical examples of equations that clearly show P≠NP. Computing in itself was originally formed from using iterative methods to solve hard problems. Least-squares methods, sin() cos(), traveling salesman, so many to list? To say P=NP for all problems seems like a fools errand to me.

[–] vanderZwan 3 days ago

See his answer to the seventeenth question in this interview:

https://www.informit.com/articles/article.aspx?p=2213858&WT....

> Don Knuth: As you say, I've come to believe that P = N P, namely that there does exist an integer M and an algorithm that will solve every n-bit problem belonging to the class N P in n**M elementary steps.

[–] dingdongditchme 2 days ago

thanks for the quote. Reading through it is clear that my understanding of P=NP is not complete enough. I would have thought n*M is precisely not polynomial but exponential time.

[–] zahlman 2 days ago

The two asterisks here represent exponentiation.

…Oh, I see. The M here is a hypothesized constant, with n as the base. That's how polynomial time looks. Exponential time would have n in the exponent.

[–] Dylan16807 10 hours ago

Clearly show it how?

It's not enough for finding a solution to be slower than verifying, it has to be slower by a particular extreme amount, and that has to hold for the best possible solution.

Also, there's a set of problems called NP-hard that you can convert any other NP problem into. For P≠NP we have to make sure all of the problems that are NP-hard have that speed difference (including the overhead from doing that conversion).

[–] kscarlet 3 days ago

Do you understand what P and NP mean?

[–] dingdongditchme 2 days ago

I am not a computer scientist so my understanding is "incomplete". I thought it stood for polynomial and non-polynomial time. But i do mix them up here and there. What i have read time and time again is that: If P≠NP would mean some problems really are harder to solve than to check (which feels intuitive given working encryption exists and all the mathematical functions that I know and understand). For example checking the roots of polynomials is easier than finding them in the first place.

[–] Ohentis 2 days ago

From this comment it isn't clear if you previously thought it stood for polynomial and non-polynomial and have been corrected or if you still have this misconception, but just in case: it actually stands for polynomial and nondeterministic polynomial. P is a subset of NP, they aren't opposites. And yes most people intuit that they likely aren't equal.

[–] dingdongditchme 2 days ago

thank you for the clarification! Turns out I still have a few things to learn.

[–] zahlman 3 days ago

We had O(n lg n) since 2019 already; now we (supposedly) know the limit is less than that (but of course at least linear).

> In 2019, Harvey and van der Hoeven came up with a galactic algorithm with complexity O ( n log ⁡ n ) {\displaystyle O(n\log n)}. This matches a guess by Schönhage and Strassen that this would be the optimal bound.

> In September 2026, OpenAI released a preprint claiming an algorithm with complexity O ( n ( log ⁡ n ) α ) {\displaystyle O(n(\log n)^{\alpha })} with α < 1 {\displaystyle \alpha <1}

https://en.wikipedia.org/wiki/Multiplication_algorithm

That said, it's interesting to contemplate that there is "space between" polynomial and exponential time complexities.

[–] lukasgelbmann 2 days ago

> “We had O(n lg n) since 2019 already”

Yes, svat’s comment accounts for that by using little-o notation* in o(n log n). This was only achieved in the 2026 result.

* https://en.wikipedia.org/wiki/Little_o_notation