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.

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It may be worth pointing out that "permanent is hard" here means "for constant and division free circuits". $\endgroup$
    – Sasho Nikolov
    Commented Feb 11, 2014 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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