# How hard is it to compute the permanent?

- ID: permanent-arithmetic-lower-bounds
- Provider: OpenAI
- Published: 2026-08-01
- Editorial check: 2026-10-29
- Status: formalized-provider-reported
- Evidence: Provider announcement; formal certificates reported, not rerun here
- Source: https://openai.com/index/ten-advances-in-mathematics/
- Public article: https://ai-tracking.sevensa.nl/en/discoveries/permanent-arithmetic-lower-bounds/

## Plain-language explanation

The determinant is a familiar way to combine a square matrix. Its cousin, the permanent, sums similar products without alternating signs. That small-looking change leads to a very different computational problem.

## Research contribution

The release reports new arithmetic-circuit and formula lower bounds, including an arithmetic-formula bound of order n⁴/log n for the permanent.

## Academic interpretation

An arithmetic formula is a restricted computation model: intermediate results cannot be freely reused as in a general circuit. Therefore a formula lower bound must not be presented as the same lower bound for all circuits or all algorithms. The underlying field, allowed constants, uniformity assumptions and circuit class are essential parts of the theorem.

## Implications

Could advance methods for proving that algebraic computations intrinsically require substantial resources.

## Caveat

This does not resolve P versus NP. A bound for one arithmetic computation model is not a universal software runtime lower bound.

This is an editorial summary, NOT an independent mathematical proof check.