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

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

CC BY-SA 3.0
2014-02-11T16:06:04.587Z
It may be worth pointing out that "permanent is hard" here means "for constant and division free circuits".
Sasho Nikolov
CC BY-SA 3.0
2014-02-11T09:45:16.557Z
2014-02-11T09:45:16.557Z
Markus Bläser
<p>I am concerned about the  following question, consider
$P_n(x)= \sum_{i=0}^n \frac{x^n}{n!}$</p>

<p>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). </p>

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

CC BY-SA 3.0
2014-02-10T15:21:10.100Z
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
CC BY-SA 3.0
2014-02-10T15:24:09.657Z
yes, it is constant-free. Thanks for comments.
maomao
CC BY-SA 3.0
2014-02-10T15:26:46.480Z
it is not a homework. The motivation is that if the answer is positive, loosely speaking one can evaluate $P_n(x)$ in a complexity class lower than Pspace for large $n$.
maomao
CC BY-SA 3.0
2014-02-10T15:35:37.493Z
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
CC BY-SA 3.0
2014-02-10T16:34:42.327Z
Borwein's method for the factorial is the asymptotically best I am aware of http://cstheory.stackexchange.com/questions/20594/factoriality-testing-algorithms-and-their-efficiency/
Chad Brewbaker
CC BY-SA 3.0
2014-02-11T07:03:44.433Z
@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
CC BY-SA 3.0
2014-02-11T09:47:11.017Z
Where in the world  is this homework? ;-)
Markus Bläser
CC BY-SA 3.0
2014-02-11T14:55:49.610Z
@MarkusBläser: the original question was *much* simpler, which is what made me think it might've been homework.
Joshua Grochow
CC BY-SA 3.0
2014-02-11T14:58:01.760Z
@Bruno: I was thinking of constant-free circuits *with* division, so that the difficulty of computing the constants could still be taken into account, even though they're not all integers.
Joshua Grochow
CC BY-SA 3.0
2014-02-11T16:05:25.537Z
BTW it is not clear that allowing constants makes the problem easy. In fact in the Bürgisser paper Markus cited, constants and divisions are allowed.
Sasho Nikolov
<cc.complexity-theory><arithmetic-circuits>
arithmetic circuits for polynomials (updated)
maomao
# arithmetic circuits for polynomials (updated)

(Asked by: username_0 on 2014-02-10)

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.

**Tags:** cc.complexity-theory, arithmetic-circuits

> **Comments:**
> **username_1**: 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.  
> **username_0**: yes, it is constant-free. Thanks for comments.  
> **username_0**: it is not a homework. The motivation is that if the answer is positive, loosely speaking one can evaluate $P_n(x)$ in a complexity class lower than Pspace for large $n$.  
> **username_1**: 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$.  
> **username_2**: Borwein's method for the factorial is the asymptotically best I am aware of http://cstheory.stackexchange.com/questions/20594/factoriality-testing-algorithms-and-their-efficiency/  
> **username_3**: @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!  
> **username_4**: Where in the world  is this homework? ;-)  
> **username_1**: @MarkusBläser: the original question was *much* simpler, which is what made me think it might've been homework.  
> **username_1**: @username_3: I was thinking of constant-free circuits *with* division, so that the difficulty of computing the constants could still be taken into account, even though they're not all integers.  
> **username_5**: BTW it is not clear that allowing constants makes the problem easy. In fact in the Bürgisser paper Markus cited, constants and divisions are allowed.  

---

## 1 answers

### Answer by username_4 on 2014-02-11. Score: 7

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.

> **Comments:**
> **username_5**: It may be worth pointing out that "permanent is hard" here means "for constant and division free circuits".  

---

