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.

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.

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.

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.

> The subexponential solution does carry over to any (?) problems that have can be reduced to 3SAT in a linear number of variables. They list: Counting independent sets, Counting proper q-colorings, Counting perfect matchings.

Wouldn't that also include functions that can be evaluated in hardware using a fixed number of gates? E.g., symmetric cryptography?

> To be clear though, it does not imply that NP is subexponential

Is there a subset of NP problems for which a subexponential algorithm would witness the entire NP class being subexponential?

Can you explain more?

SAT-solving expert here. No immediate applications (the results in the paper are "galactic"). The main question is whether some ideas here will snowball into other ideas, one of which could eventually be very practical.

The data you put into a SAT solver has substantial effect on it's performance in practice. Real world inputs tend to be much nicer than pathological ones, so I don't think there's much practical application, but I also haven't read the paper yet.

No, SETH implies quadratic time does not mean !SETH implies !quadratic time.

SETH is a much stronger claim than ETH

It's playful!

But it's also not even wrong, in the Pauli sense.

That makes me wonder if "I see your CS proof, how does this affect LLMs / nvidia stonk price???" being immediately self-described as "playful" ensures criticism looks cranky.

No, this doesn't touch NP ?= P

the presumption is that these results are a side-effect of reinforcement learning to make the models smarter.

I like this https://www.reddit.com/r/explainlikeimfive/comments/33fmrq/e...

  In computer science, the satisfiability problem is the task of determining whether a boolean problem can be satisfied, that is, made to be true, by some combination of inputs. For example, the expression: A AND NOT B is satisfied whenever A is true and B is false, while the expression: A AND NOT A cannot be satisfied.
  A naive approach to satisfiablilty would be to check every possible input and see if the expression evaluates to true. 
  However, the number of combinations that must be checked is 2n, where n is the number of variables in the expression. This is what is meant by exponential time.
  The exponential time hypothesis conjectures that you cannot do better, that is, the number of operations needed to solve satisfiability will always be exponential in the size of the problem, no matter what algorithm is chosen.
  If this hypothesis is true, it would imply that P≠NP, because satisfiability has been shown to be in NP, and in order for it to be in P there would have to exist an algorithm that solves it in polynomial time.

There's a set of problems that are (it is conjectured) easy to verify but hard to solve. One of them, called 3SAT, looks for values (a, b, c, ...) such that an expression like ((a or b or c) and (b or not-c or e) and ...) evaluates to true. And it turns out that all of these supposedly hard problems can be converted to 3SAT, so if you find a solution to one you find a solution to all.

The Exponential Time Hypothesis in effect says that 3SAT can only be solved by brute force--trying every possible combination until you find the right one. If your 3SAT expression has 100 variables, then this will take about 2^100 tries (exponential time).

What they found was an algorithm faster than brute force. 3SAT is still potentially one of these hard problems, but finding anything faster than brute force is a major advance.

The exponential time hypothesis is essentially that NP-complete problems' best solutions are all exponential.

NP-complete problems are essentially those where you need to make some kind of choice over a superlinearly-growing set of options where each option can be solved in polynomial time. Like, for example, finding a route between cities on a map under a certain total distance. You might need to go over all choices of routes.

The ETH essentially assumes that the best solution (in terms of complexity, i.e. how it grows) you can get for these kinds of problems is exponential. OpenAI just proved that this is false, you can have solutions that are below exponential complexity (but still above polynomial - if anyone finds a polynomial solution then we'd have proven that P=NP)

the language around complexity domains is really confusing.

P means "this problem can be solved in polynomial # of steps relative to the problem size"

NP means "we don't know if the problem can be solved in polynomial # of steps relative to problem size, but we know we can check if the result is correct in a polynomial # of steps relative to the problem size"

!ETH: it was widely suspected that the flagship problem in NP, 3SAT, requires an exponential # of steps relative to problem size. We now know that 3SAT requires AT MOST something more than polynomial but strictly less than exponential to solve.

"P = NP" means "if you can check it in polynomial time, there's some way to solve it in polynomial time". "P != NP" means "there are some problems checkable in polynomial time for which there is no polynomial way to obtain the result"

Today's new proof makes "P = NP" "feel more likely", because we know that the flagship problem in NP is not exponential.

3SAT can't be solved in sub-exponential time

Fwiw never thought it was a well-named conjecture

[deleted, originally wrote the hypothesis being true would imply NP=EXPTIME which is wrong, since there can be problems in EXPTIME which aren't in NP.

And the result that it's now false apparently doesn't imply NP!=EXPTIME either since it seems not strongly subexponential enough to offset the expansion in variables from reductions. See the other comments for a much better explanation.]

If I am understanding this correctly (and I am still reading this!) and if this is true, this means NP is sub-exponential. Sub-exponential does not mean P=NP. But yes, this is huge if true.

This means hard problems aren't as hard as we thought, and it's still possible P=NP. If it turns out to be true P=NP, we're a little closer to that. (I hope P!=NP!)

Every paper which assumes ETH is true might now have their conclusions be disproven.

This defeats a few hypotheses that were widely relied on.

strong exponential time hypothesis, and the titular exponential time hypothesis

It's not saying that these problems are easy, but it does demonstrate that they are much easier than previously believed. A decade ago if a human had published this kind of thing, and importantly if it held up, they would be almost certainly a strong candidate for some sort of award(s).

My (very amateur) interpretation is that this weakens confidence in P!=NP. Would like to hear from some experts in this area, if this is so or not.

Subexponential time still can mean much larger than polynomial time. There's a huge space between the two.

It’s not that it isn’t quite p=np; it actually isn’t p=np.

Still, an impressive accomplishment.

no. It's huge.

The DFT result isn't RAM specific. It holds up in multi-tape turing machines. (it is, however, galactic).

What about a particular mathematician solving a problem that couldn't be solved by other mathematicians?

(For those unfamiliar with the form: https://en.wikipedia.org/wiki/Double_dactyl )

> Perhaps this will be the push we need to finally, seriously consider the possibility that our formalisms of “efficient” and “efficiently verifiable” algorithms correspond to nothing resembling reality,

What do you mean? Do you mean that our heuristics shortcuts of treating P as efficiently solvable (and NP as efficiently verifiable) are not warranted? So far pretty much all algorithms in P that we found have small exponents. That hasn't changed, but it might change in the future.

Or do you mean something else?

Keep in mind that even most instances of many NP hard problems can be solved very efficiently in practice, because most instances ain't hard.

However we know problems that are expected to be 'easier' than NP that are hard to solve in practice. These are pretty much all the problems we build cryptography out of, because essentially these problems are in the intersection of NP and co-NP and that's expected to be smaller than NP. And cryptography has to be hard to break on average to work: a random key needs to be a good key.

> and P \in NP is actually ill-posed.

Oh, that's very simple to answer: P is not an element of NP. The question people care about is whether there's any element in NP that's not in P. In LaTeX notation P \subset NP vs P \subseteq NP.

I'm not sure what you mean by ill-posed? The question is very clear. What are you trying to say?

There is nothing immediately useful or practical from this.

> Considering that no human will be able to sift through these in no less than a team-decade

How do you figure that? For ETH, OpenAI is engaging with top experts in this area. It's unlikely that they'll need 10 man-years combined to go through the results:

> This work will be verified and shepherded by a group led by Russell Impagliazzo (UC San Diego), Ramamohan Paturi (UC San Diego), and Ryan Williams (MIT). All three are experts in algorithm design and complexity theory.

> Impagliazzo and Paturi, along with Francis Zane, are the original proposers of the Exponential Time Hypothesis, and have authored a number of influential papers on the topic over the last 30 years.

> Williams has refuted strong versions of the ETH, used ETH for hardness results, and connected algorithms and lower bounds.

math major here, I can't read the paper for shit

It is just that we never considered how advanced stochastic parrots could be so powerful when dealing with basically the whole library of acquired human knowledge and guided by experts to generate.

It is not a demerit, actually I think that it is a very elegant outcome how many problems could be solved by generation and this probably show us how language is a far more important thing than we ever thought it was.

It's a math paper written for mathematicians.

It's not possible for someone who's not a specialist in the field to understand it (unless there are more elementary proofs, of which likely none exist).

Even mathematicians take a long time to read math books and articles, especially if they go into the details. They don't read math like you would read a novel.

It's sometimes okay to look at something, go "this isn't for me", and move on. You don't need to have an opinion on everything.

Sometimes hard things are hard.

> Absolutely ridiculous they have all this compute and creative resources and cant make something more intuitive to help people understand it more natively

OpenAI has that too - open their website and ask.

I agree with you insofar that the primary motivator for these press releases is public relations and investor confidence, so it should be made as minimally hard to understand as possible just by sheer virtue that it exposes oAI to more cash thrown at them.

I totally disagree with you on the precept that all difficult to understand things need be needlessly dumbed-down/watered-down until palatable for a mass (average) audience. Requiring 'math50' before 'trig101' isn't gate-keeping in any moral sense, it's an effort to save everyones' time involved when the effort is futile.

Similarly I don't demand that haute couture fashion companies explain the style to me until 'I get it' ; I just take it for granted that i'm not going to be able to understand the entirety of the world in one lifetime.

Humans in this thread have already explained that concept with much more straightforward prose.

From the HN comment guidelines:

> Don't post generated text or AI-edited text. HN is for conversation between humans.

Disclosure doesn't address the objection (not that it wouldn't be obvious anyway). If you learned something from an AI convo, tell us what you learned, in your own words, not what the LLM said.