Two Labs Say Their Machines Broke a Rule of Computer Science. Nobody Has Signed Off Yet.

Technology

Oct 28

By Ellis Ward | October 28, 2026

On October 16, 2026, a research model inside OpenAI found a natural-language disproof of the Exponential Time Hypothesis. The following day it formalized the proof in Lean, a computer-assisted verification language. Hours after OpenAI posted the result publicly on October 26, Anthropic deposited its own refutation of the same conjecture, crediting a Claude research model that had independently reached a similar conclusion on the same day OpenAI's model did. Two of the original architects of the hypothesis are now leading the examination of one of those claims. Their first public statement was a warning: their involvement should not be taken as certification.

That sentence, from an open letter by Russell Impagliazzo and Ramamohan Paturi of UC San Diego and Ryan Williams of MIT, is the clearest summary of where this story actually stands. No independent body has confirmed either result. No peer review has been completed. OpenAI's own announcement calls its manuscripts "a form of raw research data." The question drawing attention from researchers and science journalists alike is whether the institutions that normally decide such things can move fast enough to keep pace with the machines that are now producing them.

The Exponential Time Hypothesis and its importance

The Exponential Time Hypothesis, first proposed in 1999 by Impagliazzo, Paturi and Francis Zane, holds that 3-SAT, one of the foundational problems in theoretical computer science, cannot be solved in subexponential time. Solving 3-SAT means determining whether a set of logical constraints expressed in a particular form can all be satisfied simultaneously. The hypothesis does not settle the famous P versus NP problem, but it has become a standard theoretical tool. OpenAI's announcement says the ETH has been used in hundreds of papers to derive conditional hardness results across graph theory, computational biology, databases and computational geometry. It is not a background assumption in the way gravity is; it is a working assumption upon which many other conclusions rest. Disproving it would not shatter those fields, but it would send theorists back to audit a substantial body of conditional results.

Critically, neither lab claims that auditing would produce any practical turbulence in the near term. Both papers state explicitly that the result is asymptotic, meaning it describes the theoretical behavior of algorithms at scale rather than producing any speedup for real-world constraint solving. Anthropic's own repository readme puts it plainly: "The result is purely asymptotic and says nothing about solving formulas in practice." OpenAI adds in its announcement that turning the theoretical finding into practical improvements "will require significant further research." These are not hedges added under pressure. They are in the original materials.

OpenAI's claim: timeline and what has been made public

OpenAI published a blog post on October 26 titled "Working with academic communities to build scientific understanding," announcing discoveries across three fields: harmonic analysis, complexity theory and quantum field theory. The ETH disproof sits in the complexity category. OpenAI says its system produced the natural-language disproof on October 16 and formalized it in Lean the next day. Its paper, "The Exponential Time Hypothesis is False," runs 67 pages, is dated October 17 and was revised on October 25. Both the paper and the Lean proof are available in OpenAI's public GitHub repository.

One documented nuance complicates the picture. According to a side-by-side analysis published by Papex and reporting by Okay News, the running-time bound covered by OpenAI's computer-checkable Lean formalization is weaker than the stronger bound presented in the manuscript. The two documents do not say the same thing on their most significant claim, and anyone assessing the result has to navigate that gap.

The model that produced OpenAI's proofs remains proprietary. Scientific American, in its October 27 coverage of the dueling results, reports that the exact prompts, the compute time and the chain-of-thought outputs have not been made public. The Advisory Group on Mathematics and Artificial Intelligence, an independent group hosted at the Institute for Advanced Study, has listed prompt disclosure, model name, number of attempts and compute cost as standing recommendations for AI-generated results. None of those have been provided.

Anthropic's claim: independent and concurrent, with its own caveats

Anthropic deposited its paper, "A 2^o(n) Time Algorithm for 3-SAT," on Hexagon and in its public formal-math GitHub repository on October 27. Its provenance statement is unusually direct: "The core algorithm was found on October 16 by an internal Claude research model with 14M output tokens and no human input. Anthropic researchers worked with Claude to improve the presentation." The statement adds: "Independently and concurrently, an internal model at OpenAI claims to have proven a similar result."

The attribution in that last phrase, claims to have proven, is worth noting. Anthropic is treating OpenAI's result the same way the examiners are treating both results: as a claim, not a confirmed finding. The paper itself solves the harder counting problem, known as #3-SAT, which asks not just whether a solution exists but how many solutions there are. It runs in deterministic 2^o(n) time and is formalized in Lean 4.

Anthropic's repository is described as a research artifact, licensed under Apache 2.0. The README flags a limitation the reader needs to hold: no automated check verifies that the short summary statement file accurately reflects what the full paper says. A reader who wants to confirm the correspondence has to do it manually, or by re-running the proofs through nanoda, a second, independently written proof kernel that Anthropic says it used for verification.

The math and physics claims, briefly

The ETH refutations are not the only reason the past week has drawn attention to what AI models are producing. OpenAI's announcement also covers two other domains.

In mathematics, OpenAI says its models proved Sogge's local smoothing conjecture, first proposed in 1991, in every dimension. The announcement says this would also resolve the Kakeya conjecture and Stein's restriction conjecture in all dimensions. Local smoothing had previously been proved only in two dimensions, by Guth, Wang and Zhang in 2019; Wang and Zahl proved Kakeya in three dimensions in 2025. Resolution in all dimensions, across all three conjectures, is what OpenAI's claim asserts. OpenAI says the AI output was obtained on October 18, formalized in Lean the next day, and that both the natural-language writeup and the Lean proof are public on GitHub.

In physics, OpenAI says its models produced a mathematically rigorous existence proof for certain interacting quantum field theories in four dimensions, including QCD and what it describes as a unified completion of the Standard Model, building on Balaban's approach. As a subproblem, the claim covers existence of pure Yang-Mills theory, which is part of a Clay Millennium Prize problem. The Yang-Mills existence proof was produced September 9, 2026, the QCD proof September 18, and the Lean formalization of Yang-Mills existence finished October 16. The Clay problem also requires proof of a mass gap, which remains open; Scientific American states this plainly, and the claim does not complete the Millennium Prize. The AI-produced physics materials have not been released publicly. The shepherd group for the physics result, led by Nobel laureate David Gross along with Michael Douglas, Arthur Jaffe, Igor Klebanov and Nikita Nekrasov, decided to write the work up themselves first before any release.

The examiners and what they actually said

Impagliazzo, Paturi and Williams are the examination group assigned to OpenAI's ETH claim. Impagliazzo and Paturi are two of the hypothesis's original proposers, which makes their involvement both logical and pointed. Their open letter begins: "Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny."

The letter is careful about scope and credit. The examiners say they want the examination to proceed openly, "without conferring ownership of the effort on a company or a selected group of researchers, including ourselves." They close with a conditional: "If the claim is correct, it will change an important part of theoretical computer science."

They also raise a structural problem that goes beyond this particular result. Early access to AI-produced findings, they write, creates opportunities unavailable to others. Recognition may go to whoever publishes first or has the most powerful tools. Meanwhile the labor of "checking, fixing, simplifying, explaining, and extending" results receives less credit in academic systems that reward discovery. That concern is not original to this moment; it predates AI. But the speed at which these claims are arriving is concentrating it.

OpenAI agreed to the examination group's conditions: all raw data made public, and OpenAI funding a conference on the implications. A virtual meeting of the theoretical computer science community before the end of 2026 is proposed on the examiners' site.

AGMAI and the shepherd problem

The Advisory Group on Mathematics and Artificial Intelligence, which operates independently out of the Institute for Advanced Study, has been the most direct institutional voice on process. On October 25 it published a statement recommending that AI companies not designate specific mathematicians to shepherd releases. It named five disadvantages: delayed or unequal access to results, denied agency for researchers not included, the risk of biased selection, borrowed reputation (meaning the designated mathematicians' names end up vouching for the release and shielding the lab from criticism), and the fact that such designation is unnecessary. The statement was explicit that this was no criticism of the mathematicians involved.

On October 26, the day of OpenAI's announcement, AGMAI called on OpenAI to make public without delay the natural-language and Lean outputs behind its announced existence proofs for Yang-Mills and QCD. By OpenAI's own account, the Lean formalization is complete. AGMAI's position is that there is no scientific reason for delaying the release any further.

AGMAI's standing recommendations for AI-generated results are more granular than OpenAI's current disclosures. They include posting output on scholarly repositories not controlled by the lab, with citable identifiers, and disclosing the model name, prompts, chains of thought, number of attempts, compute used and costs. On most of those points, neither lab has fully complied.

The collaboration structure

OpenAI's announced principles for external collaboration are worth describing, because they set a baseline against which later conduct can be measured. The lab says it is not requiring nondisclosure agreements, that participants are free to discuss and publish their own conclusions, that OpenAI seeks no academic credit, that participation is voluntary and unpaid, and that participants speak only for themselves. For each of the three result areas, OpenAI asked external experts to act as shepherds who would organize groups to understand the work. Those shepherds then advised three different release strategies: publish outright for the mathematics result, publish alongside an external working group for the computer science result, and let the external group decide on release for the physics result. OpenAI says publicly that it does not yet know which of those approaches works best.

OpenAI has also announced a five-million-dollar contribution to the Simons Foundation, to be managed and awarded by the foundation in support of workshops, conferences and programs helping researchers engage with AI-produced results.

Where it stands as of October 28

None of the three OpenAI results and neither ETH refutation has been independently confirmed or peer reviewed. OpenAI labels the manuscripts raw research data. The ETH examination led by Impagliazzo, Paturi and Williams is being organized now. Scientific American described the reactions among researchers approached for comment as astonished, with the examination process itself still taking shape.

The situation has no clean precedent. The verification apparatus for claims of this type, formal proofs checked by proof assistants, was designed to remove human error from mathematical argument. It was not designed to accelerate at the pace at which these labs are now depositing results, nor to handle the gap between what a Lean formalization certifies and what a manuscript claims. Lean can verify that a proof compiles under certain axioms. It cannot resolve the discrepancy Papex identified between OpenAI's formalized bound and its manuscript's stronger assertion.

What is improvised and public right now is the rest: who examines, on what timeline, under what conditions, with what credit assigned to what kind of work. Impagliazzo, Paturi and Williams have named the problem clearly. AGMAI has proposed some structural fixes. OpenAI has agreed to some conditions and resisted others. Anthropic has released more provenance detail than most, while acknowledging what its own automated checks cannot confirm.

The machinery for deciding what counts as known is being built in the open, under time pressure, with landmark-scale claims arriving faster than any existing institution was built to process.

Sources

AITechnologyOpenAIAnthropic

Ellis Ward

Ellis Ward is Reporting from the Uncanny Valley's resident expert on AI systems and research norms. He explains how models are tested, where agents break down, and what a study does and does not prove. He lives in Albany.