| Zusammenfassung |
Let $\tau(n)$ denote the minimum number of arithmetic operations sufficient to build the integer $n$ from the constant $1$. We prove that if there are arithmetic circuits for computing the permanent of $n× n$ matrices having size polynomial in $n$, then $\tau(n!)$ is polynomially bounded in $łog n$. Under the same assumption on the permanent, we conclude that the Pochhammer-Wilkinson polynomials $\prod_k=1^n (X-k)$ and the Taylor approximations $\sum_k=0^n \frac1k! X^k$ and $\sum_k=1^n \frac1k X^k$ of $\exp$ and $łog$, respectively, can be computed by arithmetic circuits of size polynomial in $łog n$ (allowing divisions). This connects several so far unrelated conjectures in algebraic complexity. |
