Anthropic Says Claude Refuted the Exponential Time Hypothesis

Anthropic reported that an internal Claude research model independently identified a subexponential algorithm for 3-SAT, a canonical NP-complete problem. The finding, if verified, would refute the exponential time hypothesis, a foundational assumption in computational complexity theory. The model also produced a paper accompanied by a Lean formalization of the result.

Results from competing models have since emerged, and the company noted that these parallel developments reinforce the need for independent mathematical review before any such claim is treated as settled. The formalization and the broader research process are being presented as a case study in how AI systems might contribute to theoretical computer science, while also highlighting the importance of community verification in establishing mathematical truth.