OpenAI said on Monday that an internal AI model produced a refutation of the Exponential Time Hypothesis (ETH), a computer-science conjecture first published in 1999, and Anthropic released its own claimed refutation hours later, according to TechCrunch (opens in new tab) and Scientific American (opens in new tab). No independent group has confirmed either claim. OpenAI’s write-up and proof are posted on GitHub, The Verge (opens in new tab) reported, so that others can examine them.

The Next Web (opens in new tab) reported that ETH concerns how hard it is to solve Boolean satisfiability problems, and that researchers have used it to show that problems in graph theory, computational biology, databases and other fields are hard to solve quickly. Scientific American (opens in new tab) described ETH as the idea that the 3-SAT problem cannot be solved in less than exponential time, and said OpenAI’s proof provides an algorithm that is “just a tiny bit faster than exponential time.” It said the result does not necessarily translate into a transformative breakthrough on the P versus NP question.

According to OpenAI, its model found the disproof on Oct. 16, and the company checked it in Lean, a language that verifies proofs by machine, the next day, The Next Web (opens in new tab) reported. In its GitHub post, as quoted by The Verge (opens in new tab), OpenAI said: “The paper gives a deterministic algorithm that exactly counts satisfying assignments of fixed-width CNF formulas in subexponential time and polynomial space. The case of 3-SAT refutes the Exponential Time Hypothesis.” TechCrunch (opens in new tab) reported that Anthropic mathematician Levent Alpöge had suggested OpenAI was building on pre-existing work, and that Anthropic released its own refutation of ETH hours later. Scientific American (opens in new tab) said Anthropic’s result was based on work by an internal Anthropic model.

Russell Impagliazzo and Ramamohan Paturi of the University of California, San Diego, who first proposed ETH, and Ryan Williams of the Massachusetts Institute of Technology were asked by OpenAI to help organize an open and independent examination of the claim, according to The Verge (opens in new tab), The Next Web (opens in new tab) and TechCrunch (opens in new tab). In an open letter, they wrote: “Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny.” They also wrote: “If the claim is correct, it will change an important part of theoretical computer science.” Williams said on X that the group signed no non-disclosure agreements and will not be paid, The Next Web (opens in new tab) reported. The group asked OpenAI to release its raw data and fund a conference, and OpenAI agreed, according to Williams and OpenAI.

Williams told TechCrunch (opens in new tab) that some parts of OpenAI’s proof are routine but that there are “two or three alien-looking parts.” He said he does not think OpenAI’s algorithm is the best possible: “I don’t think that OpenAI’s algorithm could possibly be the best algorithm you can get.” TechCrunch (opens in new tab) reported that, in Williams’s view, many papers that rely on ETH would need to be revisited if the claims hold up. He also said he asked OpenAI’s science lead, Dan Roberts, whether the work affects cryptography, and that OpenAI told him it had checked and was reasonably confident the result implies no breaks of cryptographic systems.

Scientific American (opens in new tab) reported that the model behind OpenAI’s results remains proprietary, and that the prompts, computing time and chain-of-thought outputs used have not been made public. It said OpenAI’s approach to two of the three results contradicts recommendations from the Advisory Group on Mathematics and Artificial Intelligence, an expert panel the company organized, which had issued a statement a day earlier.

OpenAI also announced two other results on Monday, The Next Web (opens in new tab) reported: a proof of the local smoothing conjecture, proposed by Christopher Sogge in 1991, in every dimension, and a proof that certain four-dimensional quantum field theories exist, including pure Yang-Mills theory, which is part of one of the Clay Mathematics Institute’s Millennium Prize problems. A physics group led by Nobel laureate David Gross will write up that work and chose not to release the AI-produced material for now. OpenAI also gave $5 million to the Simons Foundation for workshops and conferences on AI-produced results, The Next Web (opens in new tab) said.