OpenAI and Anthropic announce that internal models overturned the Exponential Time Hypothesis; conclusions await peer review

OpenAI and Anthropic successively announced that on October 16 the two companies separately used internal models to obtain results overturning the Exponential Time Hypothesis (ETH), both having provided Lean formal proofs, with the conclusions still awaiting peer review. The ETH hypothesizes that no subexponential-time algorithm exists for the 3-SAT problem, and it had previously been widely treated by the academic community as a premise, with a large number of complexity conclusions in fields such as graph theory and computational biology built on it. OpenAI's model found an algorithm that exactly counts solutions to logical formulas in subexponential time and polynomial space, and invited ETH proposers Russell Impagliazzo and Ramamohan Paturi and MIT mathematician Ryan Williams to form a group responsible for verification, and made all raw data public at the mathematicians' request. Anthropic stated that its core algorithm was independently discovered by an internal Claude model, with human researchers participating in improving the presentation. The three mathematicians published an article stating that their participation does not constitute endorsement of the claim and that they are organizing an independent review; if the conclusion is ultimately verified as valid, a large number of computational hardness judgments relying on the ETH will need to be reexamined.