OpenAI and Anthropic claim proofs overturn key computing hypothesis

OpenAI and Anthropic say their AI systems have disproved the exponential time hypothesis, a foundational assumption in theoretical computer science. The hypothesis holds that solving certain problems requires effort that grows exponentially with problem size. Neither company’s proof has been independently verified, leaving the potentially sweeping implications conditional on further scrutiny.

Both companies published their proofs on GitHub in natural language and the machine-checkable Lean format. OpenAI has asked academics to coordinate a review and committed to funding a conference on the findings. If confirmed, the results could undermine substantial research in computational complexity and algorithm design. UC Santa Barbara professor Daniel Lokshtanov estimates that around 50 of his published papers could become pointless or require revisiting.

Researchers describe a mix of excitement and psychological strain as AI-generated findings disrupt ongoing projects. Some plan to revisit problems previously considered unpromising under the hypothesis. Others warn that the growing volume of AI-produced manuscripts, including erroneous work, is placing heavy demands on researchers’ ability to evaluate results.

The findings do not directly affect cryptography, but researchers say they highlight the importance of testing computational assumptions underlying digital infrastructure. For those whose work depends on the hypothesis, the immediate task is to understand the proofs, reassess earlier conclusions and identify which new research directions become possible.