OpenAI says one of its internal models has refuted the Exponential Time Hypothesis (ETH), a widely assumed limit on how quickly computers can solve a classic logic problem called Boolean satisfiability. Many results in theoretical computer science are built on ETH being true.
OpenAI announced the claim this week alongside two others: a proof of the local smoothing conjecture, which would also settle the Kakeya and Stein restriction conjectures, and a rigorous proof that certain four-dimensional quantum field theories exist, including quantum chromodynamics (QCD), the theory of the strong force. Along the way, that work also proves the existence of pure Yang-Mills theory, part of one of the Clay Millennium Prize problems.
OpenAI says the ETH and maths results have been checked in Lean, a computer proof assistant, and it has published them on GitHub. The physics material has not been released: OpenAI says it will leave that to an outside group of physicists that includes the Nobel laureate David Gross.
Why it matters: if the claims hold, they would reshape parts of computer science, mathematics and physics. But a Lean check only confirms what was formalised, and no independent review has been completed. The ETH result will be examined by a group led by Russell Impagliazzo and Ramamohan Paturi, two of the researchers who first proposed ETH, and MIT’s Ryan Williams. According to The Next Web, the reviewers say their involvement “should not be taken as certification of the claim”.
Source: OpenAI