OpenAI and Anthropic Say Their AI Models Have Refuted the Exponential Time Hypothesis
US AI companies OpenAI and Anthropic say their models found algorithms that disprove a long-held computer science assumption, the Exponential Time Hypothesis. The scientific community is still examining the results.
OpenAI, the US artificial intelligence company behind ChatGPT, on Monday released solutions to three long-standing math problems. One is a surprise claim that the Exponential Time Hypothesis (ETH) has been refuted. ETH is a durable computer science assumption that shapes much of how researchers understand which problems are hard to compute. A few hours later, rival company Anthropic published its own refutation of ETH, after Anthropic mathematician Levent Alpöge suggested OpenAI's solutions drew on pre-existing work.
How OpenAI released the results
This time the company handled each of the three scientific fields differently. Mathematicians received the work on GitHub. Computer scientists formed a working group, asked for the proofs to be made public and requested that OpenAI fund a conference to discuss them. Physicists formed their own working group, which will decide how their result is released.
MIT professor Ryan Williams is organizing the computer science response. He had earlier criticized OpenAI's approach, calling its proof release earlier in October a "DDOS attack on mathematicians." He has now agreed to collaborate to help guide ideas he considers vital to the field. Together with UC San Diego computer scientists Russell Impagliazzo and Ramamohan Paturi, who first published ETH in 1999, he issued an open letter seeking feedback from interested scientists and a discussion of norms for AI contributions.
Why it matters
ETH is linked to the P vs NP problem: whether every problem whose solution can be checked quickly can also be solved quickly. Most scientists believe it cannot, and ETH supported that view by stating that, for a certain class of logic puzzles, even the fastest algorithm needs exponentially more time as the number of variables grows. The two companies claim their models produced algorithms that solve these puzzles in "sub-exponential" time.
Williams says this calls into question earlier intuitions, though he doubts OpenAI's algorithm is the best possible. Because many papers from the past decade rely on ETH, they would need revisiting if the claim holds. OpenAI science lead Dan Roberts told him the company checked cryptographic systems and was reasonably confident no breaks were implied.
