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

By Simon Yoon

Canonical URL: https://www.tokenpost.com/news/technology/52221
Published: 2026-11-09T10:44:49.000Z
Updated: 2026-11-09T10:44:49.000Z
Section: Technology

> The companies have proposed algorithms that would challenge the Exponential Time Hypothesis; its authors and a longtime skeptic are helping organize an independent review.

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.

Each company describes limits to its claims. Anthropic calls its result asymptotic and says it does not bear on solving formulas in practice. OpenAI says its result does not show that general NP problems have subexponential-time algorithms.

Paturi said the claims surprised him, but research built on the hypothesis over the past three decades would not disappear. Ryan Williams, an MIT scholar who has questioned the conjecture, said he felt vindicated after publicly identifying himself as a leading skeptic. Impagliazzo said he would have preferred a human researcher able to explain the reasoning to make the discovery.

Impagliazzo, Paturi and Williams are helping organize an independent review of the claims. Impagliazzo said the results are unlikely to affect the public in the short term and do not pose a current cybersecurity threat, although future extensions might make stronger encryption necessary.

Paturi said concentrated access to powerful research tools raises questions about who can participate, who gets early access and who sets research priorities. He said company announcements cannot replace academic assessment. Williams said responsibility rests with AI companies.

Paturi encouraged students to use AI tools while developing their own judgment. Impagliazzo said AI may take over solving problems, leaving people to verify and explain results until further AI progress changes that division. Williams said the field is undergoing a major change and remains worth pursuing.