AI proofs challenge a foundational computing hypothesis

OpenAI and Anthropic have published AI-generated proofs they claim disprove the Exponential Time Hypothesis (ETH), a long-standing assumption about how the difficulty of certain computational problems grows with their size. Researchers have not independently verified the findings. If confirmed, the results could force computer scientists to reconsider decades of work on algorithms and computational complexity.

UC Santa Barbara professor Daniel Lokshtanov estimates that around 50 of his published papers could become pointless or require substantial revisions. Researchers at Linköping University and the IT University of Copenhagen also describe ongoing projects as potentially undermined. Some nevertheless welcome the prospect of revisiting problems previously considered impractical under ETH.

Both companies have posted their findings on GitHub in natural language and Lean, a format that supports computerized proof checking. OpenAI has sought academic help to organize an independent examination and committed to funding a conference. Review capacity remains a concern: an earlier release of 722 manuscripts covering 400 mathematical problems drew complaints about errors and the workload involved.

The claimed results do not directly break existing cryptography, although they could prompt scrutiny of computational assumptions underlying digital security. Researchers emphasize that the proofs must survive careful examination before their consequences can be established.