Anthropic claims 3SUM bounds breakthrough with Lean-verified Claude-assisted proof

HankYeomans · x · 2026-10-07

A much-discussed result: Anthropic, using Claude, improved polynomial bounds on 3SUM-family problems — potentially a major step toward P=NP. The release scheme is notable: the proof was formalized in Lean so correctness is machine-checked, then Anthropic contacted the original authors, offering compensation and Claude access to co-write the paper. Commenters see it as a promising model for AI-academia collaboration, opening follow-up research on further exponent reductions.

Related event: Truly Subquadratic 3SUM and Subcubic APSP Break Decades-Old Barriers, Reportedly with Claude's Help(13 posts)→

Original post →

More from Research

Research channel →