AI May Have Disproved A 27-Year-Old Computer Science Theory: Report

Artificial intelligence (AI) systems developed by OpenAI and Anthropic have reportedly challenged a long-standing theory in computer science, potentially forcing researchers to reconsider decades of work. According to WIRED, both companies claim their AI systems have disproved the Exponential Time Hypothesis (ETH), a 27-year-old assumption about the difficulty of solving certain computing problems. However, researchers have yet to independently verify the mathematical proofs.

What Is the Exponential Time Hypothesis?

The Exponential Time Hypothesis suggests that certain complex computing problems cannot be solved significantly faster than existing mathematical estimates predict. Researchers have relied on this assumption to study the limits of computer algorithms and understand why some problems become extremely difficult as they grow larger.

If the claims are confirmed, some established research based on this hypothesis could require revision.

WIRED reported that Peter Jonsson, a professor at Linköping University in Sweden, believes much of his research could be affected. Daniel Lokshtanov, a professor at the University of California, Santa Barbara, also said that around 50 of his published papers could become irrelevant or require further examination if the findings are confirmed.

AI Proofs Await Independent Verification

OpenAI and Anthropic have published mathematical proofs supporting their claims. These include explanations in ordinary language and versions written in Lean, a system that allows mathematical arguments to be checked formally.

WIRED reported that researchers were examining the findings to determine whether the proofs were correct and what they could mean for computer science.

Some academics fear that years of research could need revision. Others believe the development could create opportunities to explore problems previously considered too difficult to solve.

Could It Affect Cybersecurity?

The findings could also raise questions about the mathematical assumptions behind some digital security systems. Cryptography relies on certain problems being difficult to solve within a practical amount of time.

However, the reported breakthrough does not directly break existing encryption systems. Any wider impact would depend on the details of the proofs and their relevance to cryptographic methods.

The development highlights the growing role of AI in scientific research. If the claims withstand independent scrutiny, they could mark a significant turning point in theoretical computer science.

For now, researchers must verify the proofs before concluding that decades of established thinking need to change.