Anthropic Internal Model Reportedly Solves 3SUM and APSP Open Problems

robleclerc · x · 2026-10-07

Claim: An Anthropic internal model, while probing open problems in theoretical computer science, reportedly discovered the core algorithm on its own. Researchers then simplified the discovery and proved polynomial speedups for two classic problems:

Why it matters: For decades, $O(n^2)$ for 3SUM and $O(n^3)$ for APSP were treated as fundamental barriers, with the whole subfield of fine-grained complexity built on those assumptions.

Pushback: Rob Leclerc quotes Grok's quip that you'd need $n^{602}$ to see a 2x asymptotic improvement — implying the speedup is practically meaningless at realistic scales.

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

Original post →

More from Models

Models channel →