OpenAI claims to have disproved the Exponential Time Hypothesis (ETH), a 1999 computer-science conjecture unrelated to Ethereum, its price or co-founder Vitalik Buterin. Its 67-page paper presents a deterministic algorithm that can count solutions to the 3-SAT problem in subexponential time, which the company says could guide the search for better algorithms. The proof was formalized in Lean and is undergoing independent scrutiny led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams, who stress that their involvement does not certify the claim. The result nevertheless leaves P versus NP unresolved and offers no immediate practical applications. Anthropic also presented a similar algorithm discovered by a Claude research model, noting that it concerns asymptotic analysis only.
Source: Read the original article
