- OpenAI and Anthropic independently produced subexponential algorithms that they say refute the Exponential Time Hypothesis.
- Both results have Lean formalizations, but researchers are still working to understand and scrutinize the underlying arguments.
- The breakthroughs do not resolve P versus NP or break encryption currently in use.
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.
A hypothesis from 1999, now under pressure
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.
Two labs, two refutations
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.
What the experts can and cannot verify
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.
Why this is not P equals NP, and not a broken cipher
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.
An AI research race with no finish line in sight
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.
The smartest crypto minds already read our newsletter. Want in? Join them.
FAQs
What is the Exponential Time Hypothesis?
It is a conjecture proposed by Russell Impagliazzo and Ramamohan Paturi in 1999 holding that certain Boolean satisfiability problems need time that grows exponentially with the number of variables, and it has been cited in hundreds of complexity papers.
Does refuting ETH mean encryption is broken?
No. Williams said OpenAI checked whether its result weakened cryptographic systems and was "reasonably confident" nothing was newly insecure, and Anthropic's own refutation states it is purely asymptotic with no practical effect.
How were the proofs checked?
Both labs say their refutations were verified in Lean, a formal proof language that checks each logical step, and OpenAI has published its raw proof on GitHub for a group of outside experts to examine.
Disclaimer. The information provided is not trading advice. Cryptopolitan.com holds no liability for any investments made based on the information provided on this page. We strongly recommend independent research and/or consultation with a qualified professional before making any investment decisions.
Ibiam Wayas
Ibiam Wayas has covered the crypto news beat since 2019. He studied Computer Science at National Open University of Nigeria. His work has appeared on various crypto news platforms, including Coinfomania, Crypto News Australia, and AltcoinBuzz. Drawing on his background in Computer Science, he now focuses on crypto, robotics, and longevity news.
