OpenAI and Anthropic say their AI models have produced results that challenge a long-standing assumption about the limits of computing. If the claims hold up, the findings could reshape complexity theory — though neither lab has produced faster practical software or broken existing encryption.

A hypothesis from 1999 comes under pressure

The Exponential Time Hypothesis (ETH) was proposed in 1999 by Russell Impagliazzo and Ramamohan Paturi. It holds that certain logic problems require exponentially more computational time as they grow in size, and researchers built on that assumption for decades. In practical terms, the hypothesis rules out shortcuts: it says any algorithm for these problems must slow down exponentially as inputs grow, so a subexponential method — one whose running time grows more slowly than that curve — would contradict it outright. According to OpenAI, hundreds of research papers have used the ETH to establish computational limits in fields including graph theory, databases, and computational biology. If the ETH proves false, many of those conclusions may need to be revisited.

Two labs, two claimed refutations

On October 26, OpenAI announced that one of its AI models had produced a proof challenging the ETH, as part of a broader release that also included results in harmonic analysis and quantum field theory. A Lean formalization of the result, machine-checked in the Lean proof assistant, verifies the validity of a subexponential algorithm, while the accompanying paper offers a stronger theoretical proof.

Only hours later, Anthropic presented its own findings. The company said Claude had discovered a deterministic algorithm capable of solving 3-SAT — a canonical benchmark problem in computational-hardness research — in less than exponential time, detailed in a public repository. The repository, however, notes that the discovery remains theoretical: "The result is purely asymptotic and says nothing about solving formulas in practice."

Questions also surfaced about the research itself. TechCrunch reported that Anthropic mathematician Levent Alpöge questioned how much of OpenAI's work drew on existing research.

What experts can — and cannot — verify

OpenAI assembled a review team that includes ETH pioneers Impagliazzo and Paturi along with MIT professor Ryan Williams, and agreed to support a conference and publish its findings for further scrutiny.

Williams had previously criticized the flood of AI-generated proofs, arguing that mathematicians were being overwhelmed by the volume of work requiring review. But OpenAI's latest findings intrigued him. Speaking to TechCrunch, he noted that while some parts of the proof seemed familiar, others stood out: "there are two or three alien-looking parts."

That is where human expertise matters. Lean can confirm that a formal proof is logically sound, but researchers still need to understand the unfamiliar reasoning and determine whether it could lead to practical algorithms. The conference OpenAI agreed to support, and the published findings that follow, are the next checkpoint for that scrutiny — the point at which the "alien-looking parts" either persuade the field or do not.

Not P versus NP, and not a broken cipher

Disproving the ETH would not settle P versus NP — the separate, decades-old question of whether every problem whose answers can be quickly verified can also be quickly solved — nor would it expose weaknesses in existing encryption. Still, cryptocurrency holders have reason to pay attention. Cryptopolitan previously reported Ethereum researcher Justin Drake's warning that AI-generated mathematics — including OpenAI's separate release of 722 manuscripts — could eventually threaten digital signatures. For now, that remains a warning rather than a demonstrated breach.

In July, Anthropic's Claude Mythos Preview improved an attack on HAWK, a post-quantum signature candidate, after 60 hours of research. No deployed system was affected.

An AI research race with no finish line

The State of AI 2026 report describes a widening race among Anthropic, OpenAI, and Google. Anthropic's internal measurements show Claude performing 26% of tracked model R&D work in August, up from less than 1% in February. Meanwhile, Britain's AI Security Institute reports that the length of certain cybersecurity tasks AI can complete is doubling roughly every eight months. The dueling ETH announcements landed in that landscape, where AI-assisted research output is increasingly being tracked as a measure of frontier progress.

AI is helping researchers make discoveries faster, but a mathematical breakthrough does not automatically translate into better software. Even if the ETH is overturned, practical algorithms could take years to develop — and human researchers still have much work ahead.