OpenAI, Anthropic say AI refuted the Exponential Time Hypothesis

Two frontier labs say their models knocked out a pillar of computer science. Neither result has passed outside review yet.

Take the claim seriously. Take the speedup lightly.

Two labs reached the same result within hours

OpenAI added a paper titled "The Exponential Time Hypothesis is False" to its public math repository on Oct. 26, according to the repository's change log. The log says the paper gives a deterministic algorithm that exactly counts the satisfying assignments of fixed-width CNF formulas in subexponential time and polynomial space, and that the 3-SAT case refutes the hypothesis. It shipped with a Lean formalization.

Hours later, Anthropic released its own refutation on GitHub, TechCrunch reported. Anthropic's README says a deterministic algorithm solves 3-SAT on n variables in time 2^o(n). It says "the result was discovered by an internal research Claude model," and that the Lean 4 formalization "was written by AI models."

The hypothesis says, roughly, that 3-SAT, a classic logic puzzle, can't be solved much faster than an exponential search. Russell Impagliazzo and Ramamohan Paturi first published it in 1999, per TechCrunch. A lot of complexity theory assumes it.

Machine-checked is not the same as settled

Both proofs come with formal verification in Lean, so software checks every logical step. That is more than a benchmark chart gives you.

Anthropic is careful about the limit. Its README says "no machine checks that this file says what the paper says."

That gap is where people come in. OpenAI's log says an independent working group led by Impagliazzo, Paturi and MIT's Ryan Williams will examine the proof, and that the materials went public at the group's request.

Williams told TechCrunch: "Every computer scientist should probably put a little more weight on the plausibility of P = NP, but one's weight may vary." He said some parts of the proof looked routine, but "two or three alien-looking parts" need the community to work through together.

Yes, the labs want this headline. OpenAI's own repository README warns that "some of the unformalized results could have issues," and its log records three manuscripts withdrawn on Oct. 7 over a sign error. The ETH paper is one of the formalized ones. That earns it a hearing, not a pass.

Your solver and your keys are fine this week

Anthropic says it plainly: "The result is purely asymptotic and says nothing about solving formulas in practice." Your SAT solver doesn't get faster.

On encryption, Williams told TechCrunch an improved algorithm could mean some cryptographic key sizes would be considered broken. He said he asked OpenAI science lead Dan Roberts, and "apparently, they checked, and they were reasonably confident that this didn't … imply any breaks." That is secondhand, and it is OpenAI's own check.

What does change is the research bar. Anthropic's README says Claude Opus 5.5 at high effort can rederive the refutation from a short condensed description of the idea, though with a weaker bound than the paper's. Two labs reached the same result within hours. Frontier models now produce work that takes a panel of specialists to grade.

The review group decides what this is worth

Watch the Impagliazzo, Paturi and Williams group. If it confirms the core argument, many results that assume ETH need a second look. If it finds a hole, the Lean code shows everyone where to dig.

Read the proof's verdict before the press release's.