OpenAI's math team: the Exponential Time Hypothesis is false

What happened

On October 25, 2026, OpenAI's math team published a preprint on GitHub titled *The Exponential Time Hypothesis is False*, part of a trio of claimed results across mathematics, computer science, and physics announced the same week. The ETH paper is the headline grab. The Exponential Time Hypothesis is the load-bearing conjecture under roughly half of modern parameterized complexity, and if the preprint survives review, a large chunk of textbook lower bounds collapses overnight.

ETH, formalized by Impagliazzo and Paturi in 1999, says 3-SAT cannot be solved in time 2^(o(n)) — i.e., there is no subexponential algorithm for the canonical NP-complete problem. It's a strengthening of P ≠ NP: you can believe P ≠ NP and still think 3-SAT might have a 2^(√n) algorithm. ETH forbids that. The Strong ETH (SETH) further pins the exponent down to the brute-force 2^n ceiling, and SETH is the hinge for an industry of "conditional" lower bounds — proving that problems like edit distance, orthogonal vectors, and dynamic connectivity can't be meaningfully sped up unless SETH breaks.

The preprint's abstract claims a construction that solves 3-SAT in time 2^(n^(1-ε)) for some constant ε > 0 — a subexponential algorithm, which if correct, falsifies ETH. OpenAI's accompanying announcement positions all three results as outputs of a research workflow where an internal model was essential to the discovery, not merely a lookup tool.

Why it matters

Two things matter here, and the first is bigger than the second.

The first is the math. ETH has quietly been the "sorry, this is as fast as it gets" argument for twenty years of algorithm design. When someone proves your clever idea for faster edit distance can't exist, they're usually citing SETH or ETH downstream of it. If ETH goes, every one of those papers needs a footnote at minimum, and some lose their punchline entirely. Cryptographic hardness assumptions mostly rest on different foundations — factoring, lattice problems, discrete log — so RSA and Kyber aren't suddenly broken. But fine-grained cryptography (proof-of-work schemes tuned to SETH, delay functions calibrated to orthogonal-vectors hardness) would need re-tuning.

The second thing is the sociology. OpenAI isn't saying "a researcher used GPT to check some algebra." They're framing the model as a research collaborator whose contributions were load-bearing on the proof itself. That changes what a mathematical preprint even is — the author list is one thing, but the question "who checked this?" has a new answer, and the referees don't yet have a workflow for it. Terence Tao has been writing publicly for over a year about using LLMs as scaffolding for Lean proofs, and DeepMind's AlphaProof and AlphaGeometry set the precedent that models can hit IMO-adjacent problems. But ETH is a different weight class. This is not a well-defined contest problem with a known answer shape; it's a conjecture experienced complexity theorists have spent two decades failing to break.

Early community reaction on Hacker News has been exactly what you'd expect: a mix of guarded curiosity and reflexive skepticism. The top HN comment on announcement day pointed out that an OpenAI-branded preprint claiming a complexity-theory earthquake, released on a Sunday with no accompanying author-of-note from the complexity community, is the exact pattern that precedes a quiet retraction. Scott Aaronson, who has written extensively on what would and wouldn't follow from ETH breaking, has not yet publicly weighed in — his silence is a signal in itself.

The other thing worth noting: the preprint is on OpenAI's GitHub, not on arXiv. That's not a smoking gun — plenty of serious work hits GitHub first — but it does mean the proof hasn't yet entered the normal pipeline where complexity theorists will tear it apart line by line. Preprint servers aren't peer review, but they are at least the first stop for the people who'd notice if Lemma 4.2 is quietly circular.

What this means for your stack

For 99% of working developers, the direct impact is nothing. Your SAT solver won't suddenly get faster — the preprint claims an algorithm with a subexponential exponent, but the hidden constants and asymptotic crossover points for even provably faster algorithms often sit well past any input size anyone actually solves. Z3 and CaDiCaL will keep doing what they're doing. The Cook-Levin reduction still works. P vs NP is still open.

Where it matters, if it holds:

- Cryptographic parameter choices tied to fine-grained hardness. If you've seen a paper justify a proof-of-work difficulty or a VDF parameter by citing SETH-based hardness of a specific problem, that justification is now shaky. Not broken — the actual algorithm in the preprint has to be practical, not just existent — but shaky enough to re-read before you ship. - Verification tooling. Anything built on the "problems in class X can't be solved faster than Y" family of results (a surprising amount of program-analysis theory) needs re-grounding. Most practical tools don't depend on these bounds being tight, but some marketing claims do. - Hiring and interviewing. Expect a short wave of candidates citing "ETH is false now" during algorithms interviews. It will be wrong in all the ways non-experts citing complexity results are usually wrong, and worth exactly the amount of patience you'd grant any other half-digested paper.

What this *doesn't* mean: your encryption is not broken, P ≠ NP is not resolved either way, and the Millennium Prize is not awarded. ETH is a strengthening of P ≠ NP in one direction; falsifying it is consistent with P ≠ NP remaining true. The practical cryptography stack — TLS, SSH, your password manager — is not threatened by this result even in the strongest reading.

Looking ahead

The thing to watch isn't whether the paper is right. It's the review process. If this were a human-only preprint, the shape of the next six months is well-understood: a half-dozen complexity theorists would read it carefully, one of them would find either a gap or a confirmation, and we'd know by spring. With a model credited as essential to the construction, two new questions get added — can the proof be re-derived without the model (i.e., is it a genuine proof, or a model-shaped artifact that happens to work on the examples its authors tried?), and if the model is essential to verification too, what does peer review even mean? Expect the mathematical community to insist on a Lean or Coq formalization before anyone treats this as settled, and expect that to take longer than the usual preprint-to-publication cycle. The interesting outcome isn't "ETH is false" or "ETH stands." It's whichever answer we get, and how we got there.