A.I. Just Blew Up a Key Tenet of Computer Science

The central development is OpenAI’s claim that its newest AI system disproved the exponential time hypothesis, a longstanding conjecture about how difficult certain computational problems must remain. The hypothesis, proposed in 1998, is related to - but does not resolve - the famous P versus NP question: whether problems whose answers are easy to check can also be solved quickly. The usual intuition, illustrated by Sudoku, is that finding a solution should be much harder than verifying one. If the new result holds, it suggests that unexpected shortcuts may let computers solve some problems far faster than researchers thought possible. Computer scientist Russell Impagliazzo, who helped formulate the hypothesis, described the result as shocking, particularly because an AI produced the work.

The implications are sweeping but theoretical. A sufficiently fast solving method might help computers design optimal circuits, potentially improving chip design and enabling machines to build more capable successors. In the distant future, related advances might affect encryption or drug discovery, but researchers say there are no immediate practical applications. Turning mathematical insights into useful technology can take years or decades. OpenAI’s announcement came amid hundreds of AI-generated scientific claims, and rival Anthropic also said it had disproved the hypothesis. The most provocative possibility is recursive self-improvement: AI systems using mathematical breakthroughs to improve their own design. The result therefore raises questions about future computing power without demonstrating that today’s systems can perform these feats.