Two AI labs posted ETH refutations hours apart. Impagliazzo and Paturi are reviewing them both.

On Monday, October 26, OpenAI posted a 67-page paper on its website. The byline credited an internal AI model. The claim on the first page: the Exponential Time Hypothesis is false.

By Monday night, Anthropic had posted its own paper, attributed to Claude. Same conclusion. Different approach. Hours apart.

The Exponential Time Hypothesis is a 1999 conjecture from Russell Impagliazzo and Ramamohan Paturi. It says, stripped to essentials, that you can't solve 3-SAT in less than exponential time — no algorithm can do it faster than roughly 2^(cn) for some constant c. The conjecture has served as the foundation for hundreds of hardness results in algorithms and complexity theory for 25 years. Researchers have used it to prove that dozens of problems probably can't be solved fast, because solving them fast would imply solving 3-SAT fast. If ETH is false, that scaffold of proofs needs revisiting.

So. Both labs claim to have found the thing that would topple that scaffold. In the same week.

Source spread

• OpenAI — Building scientific understanding with academic communities — hype. The announcement page. Claims a "deterministic subexponential algorithm for counting satisfying assignments in k-CNF formulas." Lean proof and manuscript released publicly.
• kingy.ai — ETH-refutation claim: SAT bounds, Lean scope and what remains unconfirmed — skeptic / academic. Best technical writeup I found. Notes the Lean formalization covers canonically encoded fixed-width formulas, which is narrower than ETH in full generality.
• Medium — Why Lean Approved It, Yet the Turing Machine Halts — skeptic. Argues the Lean proof establishes subexponential ring operations over the integers, not bit-level complexity. Under a general 3-SAT model, the author calculates the algorithm still costs 2^Ω(n) bit operations.
• AGTP on X — summary thread with Ryan Williams context — academic. Relays that MIT's Ryan Williams publicly announced the claimed refutation on October 27, naming Impagliazzo and Paturi as part of the open review organizing committee.
• Cryptopolitan — both lab claims side by side — hype / builder. Good summary of both claims. Notes Anthropic's paper is titled "A 2^o(n) Time Algorithm for 3-SAT" and claims a separate independent derivation.
• aicybr — 3-SAT, Lean proof and verification — academic. Notes that Lean verified the formal statement but does not check whether the formal statement faithfully encodes the claim ETH is usually stated as.

Pros & cons

What's real:

• A 67-page AI-generated paper with a Lean 4 formalization is a real artifact. The Lean proof is correct in the formal system. That's not nothing.
• Independent expert involvement is happening fast. The fact that Impagliazzo and Paturi are on the review committee within 24 hours of the announcement is a sign that this is being taken seriously, not just dismissed.
• Per Lance Fortnow's reported comment, the approach "looks promising." Fortnow is not a credulous source.
• OpenAI also announced Yang-Mills and Kakeya results in the same week. That's a pattern, not a one-off.
• Anthropic's independently-derived result strengthens the prior slightly. Two separate models arriving at 2^o(n) from different starting points is harder to dismiss than one.

What deserves a side-eye:

• The Lean proof covers canonically encoded fixed-width k-CNF formulas. ETH is usually stated about arbitrary 3-SAT instances. Those are not the same thing. Lean approved a formalization of a claim that may be strictly narrower than the headline suggests.
• The Medium critique — while single-authored and not peer reviewed — makes a specific technical argument: that subexponential ring operations don't imply subexponential bit-level cost on a Turing machine. If this is right, ETH survives intact. The critique is not rebutted yet.
• Anthropic posting within hours is either an extraordinary coincidence or a rushed response to a competitor's announcement. Both explanations are uncomfortable. The first implies both labs were sitting on this result without telling each other. The second raises questions about how carefully Anthropic's paper was checked before posting.
• Lean verifies proofs. It does not verify that the formal statement means what you think it means. That distinction is doing a lot of work here.

Samwise's take

What builders need to know

• ETH failures don't immediately break practical cryptography. Even a valid subexponential algorithm for 3-SAT would be impractically slow for the sizes used in encryption. The headline about "is Bitcoin safe?" is noise.
• The Lean proof is on GitHub and publicly readable. If you have Lean expertise, there's real value in reading the formal statement and comparing it to how ETH is usually encoded. The gap between those two things is the active dispute.
• Impagliazzo + Paturi + Williams have committed to open review. The original ETH authors reviewing a claimed refutation is the verification process that matters. Not news cycles.
• Anthropic's competing result should be read separately. Two papers doesn't mean one confirms the other. They're independent claims about the same conjecture. Independent failure modes are also possible.
• This is part of a pattern. OpenAI announced Yang-Mills and Kakeya results in the same week. We are probably entering a period where AI-generated formal math results arrive faster than human verification can process them. Builders who work adjacent to algorithms or cryptography should track the Williams review closely.

Further reading

• OpenAI — Building scientific understanding with academic communities — official announcement with links to paper and Lean proof
• kingy.ai — ETH-refutation claim: SAT bounds, Lean scope, what remains unconfirmed — best technical breakdown of scope
• Medium — Epistemic audit of OpenAI's ETH refutation — the main technical dissent worth reading
• Cryptopolitan — both lab claims side by side
• Emergent Mind — complexity theory explainer — context on ETH for readers who need the background