A decades-old assumption about the limits of computing may have met an unexpected challenger: artificial intelligence.
On Oct. 26, the company announced that its models had produced a proof disputing the Exponential Time Hypothesis (ETH), a longstanding assumption about how difficult certain computing problems are to solve. Researchers have relied on ETH in hundreds of studies, and the new findings could prompt them to revisit some of their conclusions.
But a mathematical breakthrough does not automatically translate into faster computers. Independent researchers still need to examine the proof, and finding practical algorithms based on the result could take considerably more work.
How OpenAI's AI challenged a foundational computing assumption
According to OpenAI's announcement, its AI models produced a proof challenging ETH on Oct. 16. The company used Lean, a tool for checking mathematical proofs, to formalize the result the following day.
ETH concerns the time required to solve certain computational problems, particularly Boolean satisfiability, or SAT. In simplified terms, it proposes that no algorithm can solve every instance of the standard 3-SAT problem in subexponential time as the number of variables increases.
The hypothesis has helped researchers establish conditional limits on how efficiently other computational problems can be solved. If ETH is false, some of those conclusions would need to be reconsidered.
OpenAI called ETH "widely believed to be true." For decades, researchers have relied on it to study the limits of computation in fields such as graph theory, computational biology, and databases.
OpenAI has made both versions of the proof publicly available. Russell Impagliazzo and Ramamohan Paturi of UC San Diego, along with MIT's Ryan Williams, will lead an independent group reviewing the findings.
A disproof could change algorithm research
If OpenAI's proof holds up, researchers may need to revisit earlier studies that relied on ETH to establish which computing problems are difficult to solve.
However, challenging a computational complexity hypothesis does not mean existing software will suddenly run faster or that complex problems will become easier to solve.
OpenAI acknowledged that more work is needed: "Finding such algorithms, and turning theoretical advances into practical improvements, will require significant further research."
Interesting Engineering also reported two other AI-generated proofs involving the local smoothing conjecture and quantum field theories. Researchers are examining these results through separate review processes.
What eWeek found: Three tests before the proof changes computing
OpenAI has released its proof and outlined plans for independent review. However, researchers still have several questions to answer before the findings can lead to improvements in real-world computing.
Research milestone | What's been done | What still needs to happen |
| Formal proof | Natural-language and Lean versions are publicly available | Independent researchers must examine and interpret the proof |
| Scientific implications | The proof challenges assumptions based on ETH | Researchers must determine which earlier findings need to be revisited |
| Practical algorithms | No faster production algorithms have been demonstrated | Researchers need to develop and test algorithms that could improve computing performance |
The significance of OpenAI's reported proof goes beyond solving a difficult mathematical problem. ETH has shaped decades of research into computational complexity, helping scientists establish limits on how efficiently certain problems can be solved.
If the disproof is validated, researchers may need to revisit findings that depend on the hypothesis, although results supported by other mathematical arguments would remain intact.
The bigger question is whether the discovery could eventually lead to better algorithms. Disproving ETH would establish that certain computational problems can be solved faster in a theoretical sense, but it would not automatically produce algorithms suitable for real-world applications.
Turning that mathematical insight into measurable performance improvements could require years of additional research.
The result also highlights a challenge for AI-assisted scientific discovery. OpenAI says its proof was formalized using Lean, which checks whether mathematical arguments follow specified logical rules.
However, formal verification does not replace independent scrutiny of a proof's assumptions, interpretation, and broader implications. Researchers must still establish what the result means for computational complexity and whether it opens meaningful new directions for algorithm development
A previous Scientific American investigation into AI-assisted mathematics illustrated how difficult it can be for mathematicians to interpret AI-generated proofs, even when formal checks support their correctness.
The challenge is not simply establishing whether a proof is valid, but understanding what makes it work and how its insights could inform future research.
What OpenAI's proof means for developers and businesses
Businesses shouldn't expect their software to run faster because of OpenAI's announcement. The company has not demonstrated improvements to database performance, optimization tools, or other software used in production.
For developers and research teams, there's more to investigate. They can review the published proof, check whether their existing research relies on ETH, and follow the findings from the independent research group.
IT leaders, meanwhile, have little reason to change their infrastructure plans or software budgets based on the announcement alone. Any future computing improvements would still need to be developed, tested, and measured against existing solutions.
If researchers eventually use the proof to develop faster algorithms, the benefits could extend to industries that rely on complex calculations and large datasets.
Until then, businesses are better off judging computing performance by what their systems can actually deliver, rather than what AI-generated mathematical discoveries might make possible.
Also read: For more on how OpenAI is addressing concerns about AI-generated mathematical research, read how its $5 million pledge aims to support mathematicians and independent verification.