OpenAI and Anthropic claim their AI models have challenged the Exponential Time Hypothesis, a long-standing assumption about how hard certain computational problems are to solve. Their findings could reshape theoretical computer science if independent researchers confirm the proofs.
OpenAI announced its result on Oct. 26, alongside two other claimed breakthroughs in mathematics and physics. Anthropic subsequently released its own proposed refutation. Both companies say their models discovered algorithms that solve certain problems faster than previously assumed possible.
The findings have attracted considerable attention, but important questions remain about verification, practical applications and the mathematical techniques involved.
What Is the Exponential Time Hypothesis?
Computer scientists Russell Impagliazzo and Ramamohan Paturi introduced the Exponential Time Hypothesis, commonly called ETH, in 1999. It concerns the computational difficulty of solving certain logical problems, particularly Boolean satisfiability problems known as 3-SAT.
ETH assumes that solving these problems requires exponentially increasing time as the number of variables grows. In practical terms, adding more variables can make a problem dramatically harder, even for powerful computers.
The hypothesis is closely connected to the famous P versus NP problem. That question asks whether problems whose solutions can be verified quickly can also be solved quickly.
Sudoku offers a simple illustration. Checking a completed puzzle is relatively straightforward, but finding the correct solution can require substantial computation. Similar distinctions underlie many difficult optimization and computational problems.
OpenAI and Anthropic claim to have developed subexponential-time algorithms for relevant satisfiability problems. Such algorithms would contradict ETH if their mathematical arguments withstand independent scrutiny.
However, disproving ETH would not establish that P equals NP. Subexponential algorithms can still require enormous computing resources and remain impractical for real-world problems.
OpenAI and Anthropic Release Competing AI Proofs
In its research announcement, OpenAI said its internal model produced a refutation on Oct. 16. The company subsequently formalized the result using Lean, a software system that checks mathematical proofs.
Anthropic published a separate algorithm and its supporting Lean formalization. The company says its research Claude model independently discovered the underlying approach.
Anthropic mathematician Levent Alpöge also raised questions about the research, including the relationship between AI-generated results and earlier mathematical work.
Although both laboratories report machine-checked proofs, independent mathematical assessment remains important. Formal verification shows that a stated result follows from its encoded assumptions, but researchers must also confirm those statements accurately reflect the original claims.
That distinction has been a recurring concern. TechAmerica.ai previously examined verification problems in OpenAI’s mathematical research, including discrepancies between written arguments and formalized proofs.
Computer Scientists Organize Independent Review
MIT professor Ryan Williams is working with Impagliazzo and Paturi to coordinate the scientific response. The researchers are inviting the broader computer science community to examine the findings and their implications.
Williams has previously criticized the challenges created by large releases of AI-generated mathematical work. He has nevertheless agreed to help organize an independent evaluation of the latest ETH claim.
The group published an open letter to researchers, requesting feedback and encouraging discussion about verification, transparency and scientific attribution.
OpenAI has agreed to release supporting research materials and fund a conference addressing the findings. The researchers’ involvement does not endorse the claimed proof.
The response reflects wider concerns about AI’s growing role in scientific discovery. A group of 25 Fields Medal-winning mathematicians previously warned that rushed AI research could undermine established standards for attribution and verification.
What Could the Findings Mean for Computing and Security?
If confirmed, the results would require researchers to reconsider many conclusions built on ETH. The hypothesis appears in scientific work involving algorithms, graph theory, computational biology, databases and optimization.
Some complexity results depend directly on ETH being true. Researchers would need to reassess those conditional findings and determine which conclusions remain valid under the proposed algorithms.
Cryptography presents another area of concern. Faster algorithms for difficult computational problems can sometimes affect assumptions used in security systems. However, researchers have not established that the reported ETH refutations break existing encryption methods.
Williams said OpenAI researchers had examined potential cryptographic implications and were reasonably confident the result did not immediately compromise deployed systems.
The findings also raise broader questions about scientific research conducted with frontier AI models. OpenAI’s other announcements involve mathematical conjectures and quantum field theory, with separate expert groups reviewing the work.
For now, the proposed ETH refutations remain subject to independent examination. Their significance will depend on whether researchers can validate the algorithms, understand their methods and establish which existing computational assumptions must change.
