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.
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)
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
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...
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.
> 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)
This is a book about this:
https://www.goodreads.com/book/show/37986693-factor-man
That premise is great.
> 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.
> 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)
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.
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.
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.
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.
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.
And vise versa, a proof that P!=NP do not exclude an algorithm that is fast enough for practical n.
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.
The 2012 movie "Travelling Salesman" is a thought provoking film that explores this scenario.
[dead]
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.
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.
Do you understand what P and NP mean?
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.
> “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