A team at Anthropic has cracked a problem that sat still for decades in theoretical computer science. According to Anthropic, researchers proved a super-cubic lower bound for the formula size of the permanent, pushing past a limit that had held since the 1980s. In plain terms: they showed that any formula computing this specific function must be bigger than we could previously prove. That’s a real advance in one of the hardest corners of complexity theory.
What stands out here is not just the result but the target. The permanent is one of the most stubborn objects in the field, and moving its lower bound at all is rare.
What the permanent is, and why it’s hard
Start with something familiar. The determinant of a matrix is a value you can compute quickly, and it powers a lot of linear algebra. The permanent looks almost identical on paper. You use the same terms, but you drop the alternating plus and minus signs and just add everything up.
That one tweak changes everything. The determinant is easy to compute. The permanent is brutally hard. Leslie Valiant proved back in 1979 that the permanent is #P-complete, which puts it among the toughest counting problems we know. Two functions that look like twins, and one of them sits at the edge of what’s tractable.
What a ‘formula size lower bound’ means
A formula is a way of building a computation out of additions and multiplications, arranged in a tree with no shared reuse. Formula size counts how big that tree has to be. A lower bound is a mathematical guarantee: proof that you cannot do the job with fewer operations than some threshold, no matter how clever you are.
Lower bounds are the holy grail of complexity theory because they tell you what’s impossible, not just what’s possible. They’re also famously hard to prove. For the permanent, the best known bound had been cubic, roughly proportional to n cubed, for a long stretch. Beating it, going super-cubic, is the headline finding Anthropic reports.
Here’s the quick comparison:
- Determinant: easy to compute, well understood.
- Permanent: #P-complete, believed to require large computations.
- Old barrier: cubic formula-size lower bound.
- New result: a super-cubic lower bound, provably larger.
Why it matters
Progress on lower bounds is how the field inches toward the biggest open questions in computer science, including the separations behind P versus NP. Every proven bound closes off a hiding place where an unexpectedly fast algorithm might have lived. Nudging the permanent past cubic doesn’t settle those grand questions, but it’s the kind of concrete step the field is built on.
There’s a second story worth flagging. Anthropic is an AI company publishing a hard math proof. That signals a growing interest in using advanced models as partners in formal reasoning, where every step has to be exactly right. If AI systems can contribute to proofs at this level, that says something about where the tools are heading.
What you can take from this
For most practitioners, this won’t change your codebase tomorrow. What it does offer is a clearer read on two trends. First, the determinant-permanent gap is a clean mental model for why some problems that look similar have wildly different costs. Keep it in your back pocket when you’re reasoning about what’s cheap and what’s expensive to compute. Second, watch the space where AI meets formal mathematics. Results like this are early signals of where machine-assisted proof is going.
The technical details, including the full proof, are laid out in the original Anthropic publication for readers who want to go deeper.