OpenAI and Anthropic both claim to have disproved ETH on the same day, but no human has checked either proof yet

OpenAI and Anthropic separately announced on the same day that they had disproved the exponential time hypothesis (ETH). ETH is a conjecture in computational complexity theory. It holds that problems such as 3-SAT cannot be solved faster than exponential time in the size of the input. It underpins many results showing that certain problems cannot be solved any faster. If the disproof holds up, the map of complexity theory will be substantially redrawn.

For now, though, the only certainty is that the claims have been made. Both companies say their proofs have been checked in Lean, but no human has yet verified their contents. OpenAI will leave verification to outside researchers. For a physics result included in the same release, it says it will have a committee rewrite the paper. How these results should be received will depend on how that verification proceeds.

Same day, two labs, separately

OpenAI presented its result at github.com/openai/math, where it posts its mathematical work, and in that repository's changelog (primary sources). On Anthropic's side, Claude reportedly disproved ETH independently on the same day (OfficeChai). Anthropic mathematician Levent Alpöge posted on X. A related paper, 2610.00577v1, also appears on Hexagon, a repository of results obtained with AI assistance.

Coverage arrived in full on October 27. TechCrunch published an explainer titled "Frontier AI labs say their models refuted the exponential time hypothesis. What does that mean?" Scientific American reported that scientists were astounded by the two companies' proofs appearing side by side.

The fact that both came out separately on the same day can be read in two ways. If two independent lines of work reached the same conclusion, that is circumstantial evidence the result is correct. On the other hand, since humans have not yet fully read either proof, having two of them simply doubles the verification work. Which reading is right will only become clear once humans have read the proofs.

What Lean guarantees, and what it doesn't

Both companies have completed checks in Lean. That is a stronger way to release results than OpenAI's mass release on October 6, when only about 42% of the work had been formalized in Lean. If a proof skips a step or contains an error, Lean's kernel will reject it.

Even so, Lean only guarantees that the formalized statement follows from the formalized assumptions. Lean cannot say whether that statement really expresses ETH, or whether the model of computation or the definition of "faster than exponential" has been misstated. Complexity-theory statements are exactly the kind whose definitions tend to drift when they are formalized. And as Thomas Hales pointed out on Tao's blog on October 9, Lean's kernel itself suffered a series of soundness bugs this summer. Passing Lean is not the end of verification. It is only the starting point for human verification.

OpenAI hands verification to outsiders and has a committee rewrite the physics paper

OpenAI says it will leave verification of the ETH result to outside researchers. For the physics result in the same release, it will have a committee rewrite the paper. Scientific American covered that physics result as a case in which OpenAI scooped human researchers on a million-dollar quantum math problem.

This approach should be read alongside criticism voiced just before. On October 25, an advisory group on mathematics and AI (AGMAI) wrote on Tao's blog that it opposed labs having mathematicians they pick themselves check AI results and then announce them. Its reasons: some people get access to the material needed for checking earlier than others, which is unfair; the mathematical community loses the ability to decide who does the checking; and the companies are shielded from criticism by borrowing the reputations of the mathematicians they pick.

Handing verification to outside researchers looks like a step toward meeting that criticism. But unless OpenAI explains who chooses the outside researchers and how, and when and to whom the material will be made available, the problems the critics raised will remain. The same applies to having a committee rewrite the physics paper. The questions there are who sits on the committee and how the rewritten paper will be published.

Verification has failed to keep up with OpenAI's math before

The day after OpenAI released its papers on October 6, it withdrew three of them over sign errors, bringing the total to 719. Mathematicians set up oai-math-revised, a hub for rewriting the papers. There, objections arose over whether prior work had been properly cited, and one more paper was dropped. There is still no count of how many papers have been fully verified. The name of the math model that produced the results has not been disclosed either.

The ETH claim comes on top of that history. The question has shifted from how many results a lab can put out to how the community verifies a single result. This time, there is also a second proof from Anthropic to compare against. Whether the two proofs follow the same path or use entirely different methods will not be known until humans read them.

What to watch next

There are three things to watch. First, whether complexity theorists publicly read the formalized Lean statement itself and confirm that it correctly expresses ETH. Second, how OpenAI selects outside verifiers and how much material it makes public. The makeup of the physics committee falls under this too. Third, whether Anthropic releases material to the same standard, so that the two proofs can be compared.

Until human verification confirms at least one of the proofs, the accurate way to describe this is not "complexity theory has been overturned" but "two labs claim so, and machine checks have been completed."