OpenAI claims AI models refute longstanding Exponential Time Hypothesis

OpenAI announced that its models have produced algorithms that solve a class of logic puzzles in sub-exponential time, challenging the Exponential Time Hypothesis (ETH) that has guided computational complexity research for decades. The lab shared the findings through discipline-specific channels: mathematicians received the proofs on GitHub, computer scientists were invited to join a working group and fund a conference, and physicists formed a separate group to decide on release procedures.

MIT professor Ryan Williams, who studies computational complexity, said the AI-generated proofs contain both routine elements and a few “alien-looking” parts that merit collective investigation. He added that while the results may prompt scientists to reassess assumptions about problem tractability, they are unlikely to represent the optimal algorithmic solution.

Williams, along with UC San Diego researchers Russell Impagliazzo and Ramamohan Paturi—who originally formulated ETH in 1999—has issued an open letter seeking feedback from the scientific community and discussing norms for AI contributions to research. He emphasized the broader impact, noting that a confirmed refutation of ETH could affect numerous papers and potentially influence cryptographic security, though OpenAI reportedly believes its findings do not immediately break existing cryptographic systems.

The debate follows earlier criticism of OpenAI’s proof releases, which some researchers described as a “DDOS attack on mathematicians.” Nonetheless, Williams agreed to collaborate with the frontier labs to help interpret the results and guide future research directions.