OpenAI, Anthropic Say AI Models Challenge 25-Year-Old Computing Hypothesis

OpenAI and Anthropic said Oct. 26 that algorithms proposed by their internal AI research challenge the Exponential Time Hypothesis, a longstanding computer science conjecture used in research on difficult problems. The hypothesis, proposed about 25 years ago by Russell Impagliazzo and Ramamohan Paturi of the University of California, San Diego, holds that some problems require exponential time in the worst case. The conjecture underpins hundreds of research papers in computer science and biology. OpenAI says its deterministic algorithm can exactly count satisfying assignments of k-CNF formulas in subexponential time. Anthropic presents a subexponential algorithm for 3-SAT and lists Claude as an author. Anthropic says an internal Claude model found the result, while an AI model produced a formal proof in Lean 4 that can be checked with Lean.

BeCrypto News shows a short excerpt and links to the publisher. The full report belongs to TokenPost.