The Exponential Time Hypothesis Is False [pdf]

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.

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

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

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

No, subexponential is not the same as polynomial time. There's sub-exponential functions that grow faster than polynomial.

The big AI companies spend millions on some of these proofs (15M was one estimate for the Naiver-Stokes thing). Had anyone has spent millions on them before this? There was a 1M prize but that certainly wouldn't convince anyone to spend orders of magnitude more to solve the problem.

Meanwhile the three letter agencies are spending billions on cryptography. They have programs that recruit students starting in high school. So maybe they are sending the spooks to suppress OpenAI's cryptography breakthroughs, or maybe they just already outspent them.

That to me is the point that isn't getting enough attention: pure math isn't that well funded. I agree as much as anyone that these proofs are an unprecedented breakthrough for LLMs, but let's keep in mind that the money they are throwing around is also unprecedented.

It’s possible they have major findings in crypto but are coordinating disclosure. The PHP bug was worked for months and only leaked a few hours early.

It’s also possible they have not found any major flaws yet. The math underlying major cryptography libraries is way simpler than these advanced proofs, and the implementations among the most scrutinized and hardened bits of code in the world.

The PHP bug paradoxically gave me hope. It was not magic; it was a logic flaw that was already known for years. And exploiting it has proved way more difficult than initially feared.

I think the premise does support the conclusion that there's some mechanism suppressing release, though.

If I were to start inferring what’s going on, it’s that findings in this space have relevance to breaking current weak cryptography.

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.

> Our result is purely asymptotic: for arbitrary 3-CNF formulas with m = 5n clauses, the bound we prove does not improve on the 2n of exhaustive search unless n > 10^10000,

So their algorithm beats standard algorithms only when you have more variables than there are atoms in the universe (10^80). Even if every atom contained a whole universe, and each atom in each universe itself contained a whole universe, iterated 100 times, your still not there.

  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.

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.

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)

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.

Fwiw never thought it was a well-named conjecture

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

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.

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

Still, an impressive accomplishment.

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?

> 10^87 variables, a point where the proposed new method surpasses the already existing sat solvers

Yeah, it's not efficient in the ordinary sense.

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.

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.

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

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.

OpenAI has that too - open their website and ask.