OpenAI and Anthropic say their models refuted the Exponential Time Hypothesis

[Reece_51]

A famous assumption in computer science may have been overturned by AI. TechCrunch reports that OpenAI and Anthropic have both released work claiming their models refuted the Exponential Time Hypothesis, known as ETH

ETH was first published in 1999 by Ramamohan Paturi and Russell Impagliazzo. It says that the fastest algorithms for certain hard problems must take exponentially more time as the number of variables grows. Many results in complexity theory rely on it as a starting point

OpenAI released solutions to three long standing maths problems, one of which claims to refute ETH by finding sub exponential algorithms for certain logic problems. Anthropic released its own refutation on GitHub hours later, after Anthropic mathematician Levent Alpöge suggested that OpenAI's work built on existing results

MIT's Ryan Williams is organising the research community's response. He said parts of the proof are routine, but that two or three alien looking parts need the attention of the whole field. He also said researchers should perhaps put a little more weight on P equalling NP being plausible, although OpenAI's algorithm is likely not the best possible. OpenAI science lead Dan Roberts said the company is reasonably confident no cryptographic systems are broken

Neither proof has been independently verified yet, so caution is essential. If the claims hold, many papers from the past decade that relied on ETH may need revising. It would also be one of the most striking examples yet of AI contributing to fundamental mathematics

Do you trust AI generated proofs of results this big? And what would it mean for computer science if ETH turns out to be false?

Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean? | TechCrunchtechcrunch.com