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$
10
  • $\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$ Feb 10, 2014 at 15:21
  • $\begingroup$ yes, it is constant-free. Thanks for comments. $\endgroup$
    – maomao
    Feb 10, 2014 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$ Feb 10, 2014 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, 2014 at 7:03
  • 1
    $\begingroup$ Where in the world is this homework? ;-) $\endgroup$ Feb 11, 2014 at 9:47

1 Answer 1

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$
1
  • $\begingroup$ It may be worth pointing out that "permanent is hard" here means "for constant and division free circuits". $\endgroup$ Feb 11, 2014 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.