OpenAI and Anthropic Say AI Has Disproved a 27-Year-Old Computer Science Hypothesis — Nobody Has Verified It Yet

Two of the world's leading AI labs have, within days of each other, claimed that their AI systems disproved a hypothesis that has shaped theoretical computer science for 27 years. OpenAI says its system proved the exponential time hypothesis false, and that the result was verified in Lean, a machine-checkable proof system. Anthropic says an internal Claude research model independently found a similar result. The proofs are public. No independent researcher has yet verified them. Until that happens, this is a claim with unusually good paperwork — not an established theorem.

What the two companies announced, how they announced it, and what would count as confirmation are all on the record. What has not happened yet is the part that settles mathematics: human experts working through the proofs and agreeing that they are right.

ETH says 3-SAT cannot be solved in subexponential time

To understand the claim, start with the problem. 3-SAT asks whether a logical formula written as a conjunction of clauses, each containing three literals, can be satisfied — whether there is an assignment of true and false to its variables that makes the whole formula true. It is the canonical hard problem of computer science, and the benchmark against which thousands of other problems are measured. The fastest known algorithms for 3-SAT take exponential time, roughly 2ⁿ for n variables, and decades of work have failed to break that barrier in general.

ETH, proposed in 1999 by Russell Impagliazzo and Ramamohan Paturi, together with Francis Zane, conjectured that this barrier is fundamental: 3-SAT cannot be solved in subexponential time. Researchers have used ETH as a ruler ever since, proving conditional lower bounds — results of the form "this problem cannot be solved faster than X, assuming ETH." OpenAI says ETH "has been used in hundreds of papers" for exactly that purpose. If ETH is false, those conditional results lose their foundation, even though the problems themselves do not get easier to solve in practice.

A man writing equations on a glass board. Generic illustration of mathematical work, not the researchers or proofs in this story — via MSA.

OpenAI announced three discoveries, with the ETH proof released first

OpenAI published its announcement under the title "Working with academic communities to build scientific understanding." It describes three new discoveries produced by its internal models, in mathematics, computer science and physics, and says the manuscripts should be understood as "a form of raw research data" rather than finished science. For each result, OpenAI recruited outside experts as "shepherds" to organise independent examination.

On dates, OpenAI is specific: its AI found the natural-language disproof on 16 October 2026 and formalised it in Lean on 17 October. The announcement also bundles two other claims from the same programme — a proof of the local smoothing conjecture in all dimensions, and a rigorous existence proof for certain quantum field theories — with the physics materials held back while human physicists write them up, unlike the computer science proof, which was released immediately.

For the ETH result, the shepherds are Impagliazzo and Paturi themselves, joined by Ryan Williams of MIT — the original proposers of the hypothesis and one of the field's leading complexity theorists. OpenAI says the group invited the community to help organise an open examination of the claim, and that it will fund a conference on the result. The company says it is not seeking academic credit for the discovery.

Anthropic published a preprint claiming a fast 3-SAT algorithm

Anthropic's contribution arrived as a preprint, not a blog post. Published on 26 October 2026 on a dedicated site, Hexagon, and on arXiv as 2610.00577v1, it is titled "A 2^o(n) Time Algorithm for 3-SAT." Its abstract states the result plainly: a deterministic algorithm for 3-SAT and the counting problem #3-SAT, running in 2^o(n) time, discovered by an internal Claude research model and formalised in Lean 4. If correct, it refutes ETH, because ETH says no such algorithm exists.

Two details deserve attention. The date, 16 October, is the same date OpenAI gives for its own discovery. And the paper does not claim human verification: at publication, the Lean development had been written by AI models and reviewed by other instances of the same models, according to coverage of the paper. No person was known to have checked it.

Lean checks proofs, not whether definitions match the claim

Both claims lean on the same kind of evidence: a formal proof in Lean, a proof assistant that checks every step of a mathematical argument mechanically. Lean is a genuine advance over a PDF preprint. A Lean proof cannot contain a skipped step or an arithmetic slip that nobody noticed, because the checker verifies each inference against the axioms. That is why both companies published Lean developments alongside their papers.

But Lean cannot check the one thing that matters most here: whether the formal definitions in the code faithfully capture what mathematicians mean by the problem. A proof assistant guarantees that theorem A follows from definition B. It cannot guarantee that definition B is the right formalisation of 3-SAT, of a deterministic Turing machine, or of running time. Anthropic's own repository documentation states the limitation directly, as quoted in independent coverage: "Lean checks the proofs, but no machine checks that this file says what the paper says."

That specification gap is where human checking has to happen. Complexity theorists must inspect the definitions and reductions and confirm that the formal statement matches the informal claim. Until then, the honest description is a claimed refutation, publicly documented, awaiting independent verification.

Mathematical formulas on a blackboard. Generic illustration of mathematical work, not the proofs in this story — via Virginia State University.

Researchers described the stakes, not a verdict

Coverage of the claims, including reporting by WIRED, describes researchers scrambling to respond — one professor estimated around 50 of his published papers would be pointless or need revisiting if the result is confirmed. Those reactions are about the stakes, not the verdict. Nobody quoted has yet confirmed the proofs. Coverage on 31 October still described the proofs as awaiting independent verification, with the shepherd group reviewing the claim without endorsing it.

The practical stakes, meanwhile, are close to zero in the short term. Both proofs concern asymptotic behaviour — how running time scales as inputs grow without bound — and the constants hidden inside the claimed bounds are enormous. Anthropic's paper states, in its own words as reported in coverage, that "our result says nothing about solving formulas in practice." Real SAT solvers will not get faster because of this. Cryptography does not break either, although one researcher told WIRED the result "should definitely scare some cryptosystem designers."

Watch the shepherd examination, Lean audits and the FOCS response

Three things will determine whether this becomes a landmark or a cautionary tale. First, the shepherd group's examination: Impagliazzo, Paturi and Williams invited the community to help organise an open examination of the ETH claim, and OpenAI committed to funding a conference on it. Second, independent Lean audits, especially of the definitions in the top-level files. Third, the field's response at the IEEE Symposium on Foundations of Computer Science, where work built on ETH was due to be presented within weeks of the announcement.

The longer-term significance is different. If confirmed, hundreds of conditional hardness results would need re-examination, and the search for faster algorithms would reopen in areas where ETH had told researchers not to look. OpenAI puts it this way: the refutation "reopens questions about how much faster these tasks could become, and may help guide the search for better algorithms." That is a research programme, not a product.

A student writing geometry on a blackboard. Generic stock photograph of classroom work, not the researchers in this story — via Pexels.

Key Takeaways

• OpenAI and Anthropic both claim AI systems disproved the exponential time hypothesis in October 2026, with Lean-checked proofs published openly. Neither claim has been independently verified by human experts.
• ETH, proposed in 1999, underpins hundreds of conditional hardness results in theoretical computer science. Disproving it would reopen the search for faster algorithms, but would not speed up practical SAT solvers or break cryptography.
• The Lean developments were written by AI models and reviewed by other instances of the same models, according to coverage; no person was known to have checked them at publication.
• Lean verifies that theorems follow from definitions, but cannot verify that the definitions match the informal mathematical claim. Closing that specification gap is the work human experts must now do.
• Shepherds Impagliazzo, Paturi and Williams are organising open examination, and OpenAI will fund a conference. Watch their conclusions, not social media verdicts.

Conclusion

Two AI labs say their systems broke a 27-year-old assumption in theoretical computer science, with machine-checked proofs to show for it. That is extraordinary — and unconfirmed. Follow the verification, not the announcement. Until it arrives, the accurate headline is not that ETH is false. It is that two labs claim it is, the evidence is public, and the checking has only just begun.

Sources

• OpenAI, "Working with academic communities to build scientific understanding" (26 Oct 2026; ETH disproof claim, shepherd model, dates): https://openai.com/index/building-scientific-understanding-with-academic-communities
• Anthropic, "A 2^{o(n)} Time Algorithm for 3-SAT", Hexagon preprint 2610.00577v1 (26 Oct 2026; abstract, provenance statement, references): https://hexagonmath.org/2610.00577v1
• Oguzhan, "Exponential Time Hypothesis False — OpenAI, Anthropic 3-SAT" (analysis of the preprint and repository detail): https://www.oguzhan.co/exponential-time-hypothesis-false-openai-anthropic-3-sat/
• WIRED reporting on researcher reactions, via syndicated copy (Jonsson, Husfeldt, Lokshtanov reactions — attributed; WIRED original not read directly in re-checks on 30–31 Oct, account corroborated by further coverage on 31 Oct confirming the proofs still await independent verification): https://dnyuz.com/2026/10/29/an-ai-breakthrough-has-made-decades-of-computer-science-research-irrelevant/
• NDTV, "AI May Have Disproved A 27-Year-Old Computer Science Theory: Report" (31 Oct 2026; corroborates WIRED reporting and the unverified status): https://www.ndtv.com/artificial-intelligence/ai-may-have-disproved-a-27-year-old-computer-science-theory-report-12262433/amp/1