arXiv:2611.03636 · v1

Get Permanent Results Faster by Counting Stars

首次提交 2026-11-03 02:57

版本更新 2026-11-03 02:57

雷达观测 2026-11-04 23:41

摘要

We show that $n \times n$ permanents can be computed with $O^*{(2-\varepsilon)^n}$ arithmetic operations over every commutative ring, for $\varepsilon = 10^{-40}$. This solves a problem stated in Knuth's The Art of Computer Programming. Our algorithm implements the classical Binet--Minc identity with dynamic programming and careful bookkeeping. It also gives algebraic branching programs of size $O^*{(2-\varepsilon)^n}$.

作者备注：16 pages