THE ESSENTIALS IN 30 SECONDS

  • Volunteers say both labs' Lean proofs pass independent checkers. One contributor reports that the step linking the proofs to a standard Turing machine model was formalized on November 6.
  • Russell Impagliazzo, Ramamohan Paturi and Ryan Williams, who coordinate the review, say their involvement is not a certification. No verdict has been published.
  • Still open: whether the formal definitions match the textbook hypothesis, and whether the sharper bound in OpenAI's paper holds. The paper's bound was not fully formalized.

On October 26, OpenAI said an internal model had refuted the Exponential Time Hypothesis (ETH). ETH is a conjecture by Russell Impagliazzo and Ramamohan Paturi that 3-SAT cannot be solved in subexponential time. OpenAI's 67-page manuscript describes an algorithm that decides and counts k-SAT solutions in subexponential time, and the company attached a proof checked in the Lean proof assistant. Anthropic posted its own refutation the same day.

What has been checked

The review has largely happened in public, through a discussion blog run by Impagliazzo and Paturi of UC San Diego and Ryan Williams of MIT. On its Lean thread, contributors have rerun both formalizations. In an October 31 report, one participant noted that OpenAI's proof had been accepted only by Lean's default kernel, while Anthropic's also passed the independent nanoda checker. On November 5, another contributor reproduced both suites on macOS. On November 6, a third participant, working with Claude agents, reported porting OpenAI's proof to another Lean library, where four checkers accepted it. The same contributor said the step from Mathlib's machine model to a standard multitape Turing machine is now formalized for both results, which ShiftDelete also reported on November 7. These are volunteer reports and have not been formally reviewed.

What experts say

A November 6 New York Times report, as summarized by AI Weekly, quoted Impagliazzo calling the result "very shocking news." The reviewers say they signed no NDAs and are not being paid. OpenAI agreed to release raw data and fund a conference, at Williams's request. According to ShiftDelete, Impagliazzo told Science he is not fully certain. The three organizers state that their involvement "should not be taken as certification of the claim."

What remains open

A Lean check only shows that a formal statement follows from its definitions. Whether those definitions capture the textbook version of ETH is still a matter of human judgment. OpenAI's Lean proof establishes a weaker bound than its paper, so the sharper bound still has to be checked. Even if the refutation stands, Lance Fortnow notes that it covers k-SAT, not NP problems in general. Outside estimates cited by the Times suggest the speedups would only appear at astronomically large problem sizes.