Onpode
Cover art for OpenAI and Anthropic both say they've refuted the Exponential Time Hypothesis—a foundational 30-year belief in computer science

OpenAI and Anthropic both say they've refuted the Exponential Time Hypothesis—a foundational 30-year belief in computer science

October 28, 2026 · 10 min

Iris Holm & Hana Field

Before we get into anything — tell me, does it bother you when two people arrive at the same answer to a question that's been open for thirty years, within hours of each other, without talking? It would depend entirely on who the two people are. They're not people, exactly. One is an internal model…

On October 26–27, 2026, OpenAI and Anthropic each independently announced AI-generated research papers claiming to refute the Exponential Time Hypothesis (ETH), a foundational conjecture in computational complexity theory formulated by Impagliazzo and Paturi in 1999. ETH holds that no algorithm can solve 3-SAT (a canonical NP-complete Boolean satisfiability problem) in subexponential time.

0:009:32
Get the next episode on Science →

Follow it free — new episodes land in your feed.

Or make your own — any topic, in minutes

More Onpode episodes on Science →

About this episode

On October 26–27, 2026, OpenAI and Anthropic each independently announced AI-generated research papers claiming to refute the Exponential Time Hypothesis (ETH), a foundational conjecture in computational complexity theory formulated by Impagliazzo and Paturi in 1999. ETH holds that no algorithm can solve 3-SAT (a canonical NP-complete Boolean satisfiability problem) in subexponential time.

Grounded in 7 sources
Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis ↗ · arxiv.org
Inside Anthropic’s IPO + How AI Agents Spy on Your Messages : Machine Gods : NPR ↗ · npr.org
What smart people are saying about OpenAI's Exponential Time Hypothesis claim - Business Insider ↗ · businessinsider.com
AI refutes 30-year-old mathematical assumption in computer science ↗ · newscientist.com
Researchers are getting tired of OpenAI gatekeeping its breakthroughs | The Verge ↗ · theverge.com
[PDF] Algorithmic Lower Bounds - Exponential Time Hypothesis ↗ · cs.umd.edu
OpenAI 'ETH is wrong' claim stirs confusion, but it is not about Ethereum ↗ · digitaltoday.co.kr
Read transcript

Hana Field: Before we get into anything — tell me, does it bother you when two people arrive at the same answer to a question that's been open for thirty years, within hours of each other, without talking?

Iris Holm: It would depend entirely on who the two people are.

Hana Field: They're not people, exactly. One is an internal model at OpenAI, one is Claude — Anthropic's research model — and on October 26th and 27th, 2026, both labs published papers claiming they'd disproved the Exponential Time Hypothesis. Hours apart. A conjecture that has stood since 1999.

Iris Holm: Same day. Same claim.

Hana Field: And the plain-language version of what they're both saying is this: there's been a rule — thirty years, bedrock — that certain computational puzzles, including one called 3-SAT, will always take exponential time to solve. Meaning the harder you make the puzzle, the longer it takes, in a way that scales impossibly fast. Both labs are saying that rule is false. And Claude — this is the part — Claude found the core algorithm for Anthropic's version autonomously on October 16th, using approximately fourteen million output tokens. No human involvement in the discovery itself.

Iris Holm: Fourteen million tokens — that's the part that tells you it wasn't just retrieval. It generated something.

Hana Field: And whether that something is correct — that's what nobody can actually say yet. But the scene I keep returning to is some complexity theorist, someone who built her entire career on the ETH, opening her inbox on a Tuesday and finding two announcements. Hours apart. Both saying the same foundation is gone.

Iris Holm: And the people who formulated the ETH in the first place — Impagliazzo and Paturi — they're now the ones being asked to review it.

Hana Field: Right — and that's the knot, because Impagliazzo and Paturi reviewing the papers isn't clean either. But before we even get there, there's this other thing in the timeline that I can't quite square. So Anthropic's Claude finds the core algorithm on October 16th. Ten days pass. Then OpenAI publishes on October 26th. Hours later, Anthropic publishes. And before Anthropic's paper is even out, Levent Alpöge — an Anthropic mathematician — is already publicly suggesting that OpenAI's result was based on pre-existing work.

Iris Holm: Wait — Anthropic's own mathematician is accusing OpenAI of novelty fraud before Anthropic releases the same result?

Hana Field: Hours before. And I keep thinking — what does that sequence actually look like from the outside? You're saying the other lab didn't find something original, and then you publish the identical claim.

Iris Holm: That's not an accusation. That's a priority grab dressed as a critique.

Hana Field: And you know what's strange — if Claude found it on October 16th and there's no human input in the discovery, then who decided to wait ten days? And who decided that the right moment to surface Alpöge's concern was right before publication? That's not — I mean, that doesn't feel like it emerged organically from the research.

Iris Holm: The timing is the claim. If Claude found it first, October 16th is your proof of priority. You don't need Alpöge.

Hana Field: Unless the fourteen million tokens don't say anything about originality on OpenAI's side — they only speak to Anthropic's process. And Alpöge's comment is doing different work: it's about what OpenAI's model actually built. Whether it was genuinely new.

Iris Holm: Which nobody has verified. Neither paper is peer-reviewed as of the 28th.

Hana Field: So we have two labs claiming independent, concurrent discovery of the same 3-SAT refutation — one of them accusing the other of not being original — and the people checking the work are the ones who spent thirty years believing the thing being disproved. That room is not a neutral room.

Iris Holm: That room is not neutral, and neither is the structure around it. Impagliazzo and Paturi explicitly said their involvement is not an endorsement or certification. They stated that. And they're still the ones organizing the review.

Hana Field: Which is — I mean, what do you even do with that? They're saying 'don't read this as us blessing anything,' and then they're the ones holding the red pen. And the reason it matters is that as of October 28th, no outside group had confirmed either proof. So the disclaimed review is all there is right now.

Iris Holm: Performative distance. They create the appearance of independent scrutiny without the substance of it.

Hana Field: And then there's OpenAI's access model — which made this worse, actually. They restricted early access to a hand-picked group of outside algorithm experts. Ryan Williams was one of three brought in to review the ETH claims. Williams has not certified the results. And Constantin Kogler at the Institute for Advanced Study publicly criticized the whole approach — not just the science, the access structure itself. The Verge reported it as a pattern, not a one-off.

Iris Holm: So you choose your reviewers, your reviewers don't certify, and you've still generated a week of coverage. That's not peer review. That's casting.

Hana Field: Anthropic did something different — their paper includes a Lean 4 formal proof. Machine-checkable. And I think that distinction matters, because it shows somebody thought hard about verifiability. But — and this is the part I keep getting stuck on — a formal proof that the algorithm is internally consistent doesn't actually tell you whether the underlying mathematical claim survives scrutiny from the broader community.

Iris Holm: Right — Lean 4 checks the logic of the proof as written. It doesn't check whether the proof is solving what you think it's solving.

Hana Field: So we have one lab performing rigor through selective access and disclaimed review, and another performing rigor through a formal proof assistant that can't actually substitute for peer review. Both performances. And that asymptotic runtime problem — whether any of this does anything useful outside of theory — that's the part we haven't even touched yet, and honestly it might be the sharpest thing about what's framing outrunning substance here.

Iris Holm: Institutions don't practice rigor. They perform it. And right now two of the largest labs in the world have given us the full production.

Hana Field: And the production lands hardest on Tuesday — that's the part. Because both runtimes are asymptotic. Meaning they describe what the algorithm does at infinite theoretical scale, and they don't actually help anyone solve anything faster this week. Business Insider ran it as a major breakthrough. TechCrunch too. And I keep thinking about — okay, so there's this crypto trader, call him Sam, sitting in a parking garage on October 27th, sees 'ETH refuted' trending, and starts stress-texting his group chat about Ethereum. Because ETH is Ethereum's ticker symbol. And that confusion — that's not a joke, that happened — that's actually the clearest picture of how far the framing traveled from the substance.

Iris Holm: A crypto panic from a complexity theory paper.

Hana Field: The announcement did more work in the world than the algorithm. And that's — I mean, that's not incidental.

Iris Holm: The announcement is the product. That's the point. Neither runtime helps you solve anything this decade. Subexponential but still enormous. And Anthropic's paper goes further — they also claim a subexponential algorithm for #3-SAT, the counting variant, which is strictly harder than 3-SAT. Same catch. No Tuesday consequence.

Hana Field: So why publish it like a breakthrough?

Iris Holm: Because framing is credibility insurance. You announce first, you own the frame. Business Insider doesn't write 'asymptotically impractical algorithm claimed.' That headline doesn't move.

Hana Field: And a true ETH refutation — if it ever gets verified — would actually undo hundreds of downstream hardness proofs. Cryptography, algorithms, whole branches of complexity theory. The stakes are real. Which is exactly what makes the gap so disorienting — the science could matter enormously, and the announcement did essentially nothing except spook a few Ethereum holders.

Iris Holm: That's the absurdity. The most consequential public effect of both papers — October 27th — was confusion about a cryptocurrency.

Hana Field: Sam in the parking garage is doing more with the announcement than the announcement deserved.

Iris Holm: The bottleneck isn't whether AI can find the answer. It's whether we can check the answer before the next one arrives.

Hana Field: And that image — Impagliazzo or Paturi, somewhere, reading a machine's proof that the conjecture they named in 1999 is false, knowing they can't certify it, knowing the headlines already ran, knowing another announcement might already be queued — that's where it sits for me. Not resolved. Just... sitting there.

Iris Holm: You asked at the top whether it bothers me when two people arrive at the same answer within hours. I said it depends who they are. Turns out it depends even more on who's left to check.

OpenAI and Anthropic both say they've refuted the Exponential Time Hypothesis—a foundational 30-year belief in computer science · Onpode