# arithmetic circuits for polynomials (updated)

I am concerned about the following question, consider $P_n(x)= \sum_{i=0}^n \frac{x^n}{n!}$

Is there a straight line program (or arithmetic circuits) of polynomial size (wrt $n$) for the polynomial $P_{2^n}(x)$? The difficulty seems to lie in the factorial, as for example the polynomial $x^{2^n}$ has a polynomial size arithmetic circuit (by repeated squaring).

Sorry in my previous post I did not make the question clear, as it would become a very simple question.

• 1) You might want to specify "constant-free straight line program," since otherwise a standard assumption is that constants are free. 2) What is your motivation? I could see this being a homework question, though I could also see this being a non-homework question. – Joshua Grochow Feb 10 '14 at 15:21
• yes, it is constant-free. Thanks for comments. – maomao Feb 10 '14 at 15:24
• To make the question even clearer you could just define $P_n(x) = \sum_{i=0}^{2^n} x^i/i!$ in the first place, and point out that the summation goes all the way up to $2^n$. – Joshua Grochow Feb 10 '14 at 15:35
• @JoshuaGrochow The coefficients of the polynomial are not integers, therefore I do not know what it means for a circuit computing $P_n$ to be constant-free. Usually, constant-free circuits have no division... Of course it is not possible here to be constant-free and division-free! – Bruno Feb 11 '14 at 7:03
• Where in the world is this homework? ;-) – Markus Bläser Feb 11 '14 at 9:47

## 1 Answer

I assume that you mean $P_n(x)= \sum_{i=0}^n \frac{x^i}{i!}$.

Peter Bürgisser shows that if this problem is hard, then computing the permanent is hard (http://link.springer.com/article/10.1007/s00037-009-0260-x). To my best knowledge, your problem is open.

• It may be worth pointing out that "permanent is hard" here means "for constant and division free circuits". – Sasho Nikolov Feb 11 '14 at 16:06