OpenAI and Anthropic assert that their AI models have posed a challenge to a traditional view concerning the limits of computing. If proven true, the findings can reshape complexity theory. H
OpenAI and Anthropic assert that their AI models have posed a challenge to a traditional view concerning the limits of computing. If proven true, the findings can reshape complexity theory. However, neither of the firms has succeeded in creating faster software or in cracking current encryption.
Russell Impagliazzo and Ramamohan Paturi first proposed the Exponential Time Hypothesis (ETH) in 1999. The ETH suggests that there are specific logic problems that require exponentially more computational time as they increase in size.
Researchers built on this assumption for decades. According to OpenAI, the number of research papers that used the ETH in proving computational limits in graph theory, databases, computational biology, and so on amounts to hundreds. If ETH proves false, researchers may have to revisit many of those conclusions.
On the 26th of October, OpenAI announced that its AI model has given proof that challenges the ETH. This announcement was part of a wider release which included results in the area of harmonic analysis and quantum field theory. The Lean method of formalization proves the validity of a subexponential algorithm, although the accompanying paper provides a stronger theoretical proof.
Only hours later, Anthropic put forth its own discoveries. Claude was said to have discovered a deterministic algorithm that could solve 3-SAT in less than exponential time, according to the company. But its repository also established that the discovery is still only theoretical:
The result is purely asymptotic and says nothing about solving formulas in practice.
Questions about the research behind the discoveries also emerged. TechCrunch reported that Anthropic mathematician Levent Alpöge questioned how much of OpenAI’s work drew on existing research.
OpenAI vs. Anthropic: ETH Breakthroughs and AI Research Performance
OpenAI organized a team formed by ETH trailblazers Impagliazzo and Paturi with professor from MIT Ryan Williams to analyze the results. It also agreed to support a conference and make its findings public for further review.
Williams had previously criticized the flood of AI-generated proofs, arguing that mathematicians were being overwhelmed by the volume of work they needed to 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 becomes important. Lean can check whether the formal proof is logically sound, but researchers still need to understand the unfamiliar reasoning and determine whether it could lead to practical algorithms.
Disproving ETH does not settle P versus NP or expose weaknesses in existing encryption.
Still, cryptocurrency holders have reason to pay attention. Cryptopolitan 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, not 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.
The State of AI 2026 describes a growing race between 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 duration of certain cybersecurity tasks AI can complete is doubling roughly every eight months.
AI is helping researchers make discoveries faster. But a mathematical breakthrough does not automatically lead to better software. Even if ETH is overturned, practical algorithms could take years to develop. Human researchers still have much work ahead.
If you're reading this, you’re already ahead. Stay there with our newsletter.
