The ETH "Refutation" Is a Verification Story, Not a Math Story
Frontier labs are reportedly claiming their models refuted the Exponential Time Hypothesis, and TechCrunch's coverage leans on an MIT computer scientist drafted to explain what that even means. The headline writes itself: a machine has apparently overturned a 27-year-old pillar of computational complexity.
I don't believe it yet. But the reason I don't believe it isn't that AI can't do math. It's that "refuted ETH" is a claim whose truth is cheap to assert and expensive to check, and the labs appear to have shipped the assertion before the checking apparatus existed. That's the real story — not the conjecture, but the gap between how we announce machine-generated results and how we validate them.
What ETH actually claims
The Exponential Time Hypothesis, formulated by Impagliazzo and Paturi around 1999, is a strengthening of P ≠ NP. It says 3-SAT — the canonical NP-complete problem — cannot be solved in 2^o(n) time, where n is the number of variables. Not "no polynomial algorithm." Something much stronger: no algorithm that beats brute force by more than a subexponential-in-n factor.
ETH is not proven, and nobody expects a proof soon. Its job in the field is to be assumed, the way physicists assume constants. Under ETH you get a huge family of conditional lower bounds: that your near-quadratic edit-distance algorithm is essentially optimal, that clique has no f(k)·n^o(k) algorithm, that set cover, Steiner tree, longest common subsequence, and dozens of parameterized problems can't be improved by much. Fine-grained complexity is largely an edifice built on top of this one unproven assumption.
So "refuting ETH" means exhibiting a 3-SAT algorithm running in 2^o(n) — say 2^(n/log log n) — with a correct proof of that runtime bound.

图示:来源页预览图(仅作编辑上下文;版权归属原发布方) · 来源引用:techcrunch.com
What a refutation would and wouldn't do
It would not mean SAT is now practical. An algorithm running in 2^(n/log log n) is still exponential; it's a statement about asymptotics, not about your solver's performance on real instances. It would not break RSA or AES. It would not give P = NP.
What it would do is deflate a large chunk of algorithmic research. Every paper that says "we show this problem requires n^(2-ε) time unless ETH fails" would need a rewrite. Some cryptographic constructions whose parameter choices lean on fine-grained hardness assumptions — memory-hard functions, certain proof-of-work designs, some FHE settings — would need re-parameterization. That's a serious but bounded consequence.
The evidence problem
Here's my objection, and it's structural rather than aesthetic. A claimed algorithm is a constructive artifact. In principle, this claim is unusually checkable: you can read the algorithm, you can prove its runtime, you can implement it. Compare that to a claimed proof of the Riemann Hypothesis, where checking requires experts to internalize thousands of pages of novel argument. ETH refutation has a short, falsifiable core.
Which makes the reporting confusing. If the artifact exists and is checkable, why is the story "labs say" rather than "here is the algorithm, run it"? The most likely explanations, in descending order of probability:
- The model refuted something narrower — a lemma in a specific paper, or SETH, or an assumption internal to one proof — and the framing inflated it.
- The algorithm exists but the runtime proof has a gap that survived the lab's internal review, which is exactly the failure mode LLMs are best at producing: fluent, plausible, subtly wrong.
- The result is real, and the announcement is just badly staged.
The single most important question to ask is the one almost nobody is asking in the coverage: which statement was refuted? ETH, SETH, and "Lemma 4.2 of a 2019 paper" are three very different claims, and they collapse into one headline.
The strongest version of the labs' case
Let me steelman it, because the reflexive dismissal is also lazy.
LLMs have gotten genuinely good at the search half of mathematics: generating candidate constructions, spotting analogies across subfields, exhausting case analyses that humans abandon. For a problem like ETH — where the goal is an algorithm, and algorithms can be generated and then empirically probed — the feedback loop is tighter than for pure proof problems. A model that proposes an algorithm can be run against a benchmark and beat the state of the art on medium instances before anyone proves anything. That's a real signal, and it's the kind of signal humans are slow at producing.
And the base rate isn't zero anymore. The last two years have moved AI-assisted mathematics from "novelty" to "occasionally credited in real papers." If even one in fifty of these claims survives, the aggregate effect on the field is large — which argues for building the checking infrastructure now, not for waiting until a claim survives.
My position
The probability that ETH is false is low — call it under 5%. The probability that the labs have discovered something real and mislabeled it is high. And the reporting, which outsources the explanation to a computer scientist rather than the verification to someone with the artifact in hand, is doing the field a disservice by treating a checkable claim as a mystical one.
Opinion, stated plainly: the scarce resource in machine mathematics is no longer generation. It is adjudication. Labs that want credit for results like this should be required, by norm if not by rule, to publish the artifact — algorithm, proof, formalization, benchmark — and let the claim stand or fall on it. A press release is not a proof, and the fact that the claim is checkable makes the absence of the check harder to excuse, not easier.
What would change my mind: an explicit algorithm, a constructive runtime proof that survives expert audit, and a scaling curve on independent instances whose exponent is measured over a range wide enough to distinguish 2^0.01n from 2^(n/log log n). That's a concrete, achievable bar. If it's met, I'll be delighted to be wrong.

图示:HEXOPS 原创配图(受选题启发,非复制原文图片) · 来源引用:techcrunch.com
30-day action plan
Days 1–3 — Read the artifact, not the coverage. Locate the primary document. Enumerate exactly what was released: pseudocode, runtime proof, formalization (Lean/Coq/Isabelle), benchmark data, code. Note what's missing. Write down the precise statement claimed to be refuted, in one sentence. If you can't, that's your answer.
Days 4–7 — Reproduce the empirical slice. Take the smallest published benchmark and re-implement. Check the scaling exponent over the widest instance range you can afford. A curve fit over three decades of n is evidence; over half a decade it's noise. Compare against a strong baseline solver, not the model's own numbers.
Days 8–14 — Audit for the standard failure modes. Read the runtime proof looking specifically for: hidden dependence on machine word size, amortization that assumes what it's proving, non-constructive "for sufficiently large n" constants, oracle assumptions smuggled in as preprocessing, and a "subexponential" bound that only hides a constant in the exponent. These are the signatures of LLM-generated proofs that pass a skim.
Days 15–21 — Map your exposure. Enumerate every conditional lower bound, parameter choice, and security argument in your own work that cites ETH or SETH. For each, write one line: "if ETH fails, this becomes ___." Most will say "a faster algorithm exists, nothing breaks." A few won't. Knowing which is the actual deliverable of the month.
Days 22–30 — Set standing policy. Pre-register the evidence bar your team will apply to any AI-generated theorem claim before acting on it: artifact published, formalization or independent audit, reproduction on independent data. Adopt "artifact-first" as an announcement norm internally, so your own team doesn't ship the mistake the labs just made. Then revisit this claim — and the next one — against that bar.
Sources
- TechCrunch, "Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?" — https://techcrunch.com/2026/10/27/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean/
- Impagliazzo, R. & Paturi, R., "On the complexity of k-SAT," Journal of Computer and System Sciences (2001) — origin of ETH and SETH.
- Impagliazzo, R., Paturi, R. & Zane, F., "Which problems have strongly exponential complexity?" (1998).
- Backurs, A. & Indyk, P., "Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)," STOC 2015 — representative conditional lower bound.
- Vassilevska Williams, V., "Hardness of Easy Problems: Basing Hardness on Popular Conjectures," ISAAC 2015 — accessible survey of the fine-grained landscape.



