6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Joshua Grochow Feb 10 '14 at 15:21
  • $\begingroup$ yes, it is constant-free. Thanks for comments. $\endgroup$ – maomao Feb 10 '14 at 15:24
  • 1
    $\begingroup$ 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$. $\endgroup$ – Joshua Grochow Feb 10 '14 at 15:35
  • 1
    $\begingroup$ @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! $\endgroup$ – Bruno Feb 11 '14 at 7:03
  • 1
    $\begingroup$ Where in the world is this homework? ;-) $\endgroup$ – Markus Bläser Feb 11 '14 at 9:47
7
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.