Two rival AI labs say their models just killed one of theoretical computer science's load-bearing assumptions. On the same day. With the same discovery date. And the people now checking the work are the ones who invented the conjecture in the first place.
OpenAI posted a paper Monday titled "The Exponential Time Hypothesis is False," claiming an internal model found the disproof on October 16. About six hours later, Anthropic added its own claimed refutation to its formal-math repository, credited simply to "Claude, Anthropic" — an internal Claude research model that, according to WebProNews, found the core algorithm "with 14M output tokens and no human input." Both labs say their models arrived at the result independently, on October 16, without knowing what the other was doing.
The Exponential Time Hypothesis, or ETH, says the logic problem known as 3-SAT can't be solved meaningfully faster than brute force. It's a stronger assumption than P ≠ NP, and hundreds of papers in graph theory, computational biology, databases, and geometry derive "you cannot do better than this" results by assuming it holds. A literature search run by Claude found more than 800 papers that prove at least one result only under ETH or a hypothesis that implies it. If the refutation holds, those results aren't wrong — they're simply no longer proven.
The strangest part of the story isn't the claim. It's the review. OpenAI asked Russell Impagliazzo and Ramamohan Paturi of UC San Diego — who proposed ETH with Francis Zane — and MIT's Ryan Williams to lead the outside group verifying the proof. All three are working unpaid, signed no nondisclosure agreements, and wrote in an open letter that their involvement "should not be taken as certification of the claim." Williams, for his part, told TechCrunch he expects the result to be the beginning, not the end: "I don't think that OpenAI's algorithm could possibly be the best algorithm you can get."
Both labs backed their papers with Lean formalizations — machine-checked proofs published on GitHub. But a Lean check has a limit both labs acknowledge: as Anthropic's repository puts it, "Lean checks the proofs, but no machine checks that this file says what the paper says." No outside group has confirmed either proof yet.
And for anyone actually running a SAT solver, nothing changes this week. Anthropic's paper is blunt about it: its bound doesn't beat exhaustive search until a formula has more than 10 billion variables, and "our result says nothing about solving formulas in practice." OpenAI's paper says the same in its own way — getting real-world gains "will require significant further research" — and notes the result "does not bear on the P vs NP question directly, nor does it yield any practical algorithms for NP-complete problems."
That's the honest framing, and it's also why this matters beyond one conjecture. The ETH claim was one of three results OpenAI released Monday — it also published a proof of Sogge's local smoothing conjecture, which it says settles the Kakeya and Stein restriction conjectures, while a physics group led by Nobel laureate David Gross holds back AI-generated material on quantum field theory to write it up itself. This comes weeks after OpenAI dumped hundreds of AI-generated math manuscripts on the community at once, which Williams called a "DDOS attack on mathematicians," and days after a Microsoft researcher and a collaborator resolved the KLS conjecture with human-directed AI.
The bottleneck in frontier math is no longer producing results. It's checking them — and right now, the checkers are three unpaid professors working from PDFs, while the machines that wrote the proofs are locked inside two private labs.
— via WebProNews