Arithmetic formula complexity of the permanent
Follow the latest progress by email.
How large must a division-free arithmetic formula, or a valid rational formula, computing the complex n×n permanent be? Formula size here counts variable leaves in a tree, rather than gates in an unrestricted circuit.
Why it matters and what counts as progress
Why it matters: Formula lower bounds locate limitations of tree-shaped arithmetic computation without claiming the same limitation for general circuits.
What counts as progress: A stronger permanent-specific lower bound, such as order n⁴/log n, with the coefficient field, rational operations and size convention fixed.
How the problem developed
- 1991 · Lower bound [1]
Noam Nisan Proved exponential formula lower bounds for the permanent in the noncommutative model; commutative arithmetic formulas remained much harder.
OpenAI Astra Chapter 5 reports at least n⁴/(128 log₂ n) variable leaves for division-free formulas and n⁴/(192 log₂ n) for valid rational formulas computing the n×n permanent over ℂ, for n≥32.
AI contribution
Ten Advances in Mathematics and Theoretical Computer Science
For the n×n permanent over the complex numbers and n≥32, Chapter 5 gives at least n⁴/(128 log₂ n) variable leaves for division-free arithmetic formulas and n⁴/(192 log₂ n) for valid rational formulas. A separate circuit lower bound has different scope.
Sources
Website timeline
Publication dates and editorial changes.