OpenAI says its AI disproved the Exponential Time Hypothesis

OpenAI says one of its systems has shown that the Exponential Time Hypothesis, known as the ETH, is false. The company announced the result on Monday along with two others, one in mathematics and one in physics. None has been confirmed by anyone outside the company.

Nothing changes for everyday users. OpenAI itself says turning the disproof into useful algorithms "will require additional research."

The ETH holds that solving SAT, the problem of deciding whether a logical formula can be satisfied, takes exponential time. It was proposed by Russell Impagliazzo, Ramamohan Paturi and Francis Zane, and hundreds of papers rely on it to show that other problems are hard.

The Lean file OpenAI published spells out what was proved: for a fixed k, a deterministic machine counts the solutions of a k-CNF formula in subexponential time. Lean is a language for checking proofs by computer. OpenAI says its system reached the disproof on Oct. 16 and formalized it a day later.

That does not settle P versus NP. The running time described is subexponential, not polynomial. And it remains to be checked whether the statement written in Lean matches "the ETH is false" in its original form.

Three results, three stages

OpenAI calls the manuscripts "raw research data" and says it invited specialists to examine them, with no confidentiality agreements and no payment. In physics, the group decided against publishing the AI-generated texts and will write its own version.

Nor does OpenAI claim to have solved the Yang-Mills problem as the Clay Institute poses it, one of the Millennium Prize Problems. Its proof covers the existence of the pure theory, only part of it.

OpenAI is also putting $5 million toward the Simons Foundation, which will run workshops and conferences on results obtained with AI. The company will fund a conference on the consequences of the ETH, with no date set.