Suppose we are given a polynomial in the single variable $n$ as a prefix-free expression in the language $\{\times, +, -, 0, S, n\}$. For example, the polynomial $n^2+3n+1$ can be expressed as $+ \times nn + \times SSS0 n S0$, or as $+ n \times Sn Sn$.

Given such an expression, is there a polynomial-time algorithm to find an integer adjacent to a real root of the polynomial $P(n)$ it corresponds to if a real root exists?

We can't multiply it out to find its coefficients, since the middle ones may be super-polynomial in size. Also it's not known how to test if $P(n)$ is identically $0$ in polynomial time — so we can't know whether or not all values of $P(n)$ are roots, but all I want to do is find an integer near a root.

We can find its degree, and by computing finite differences we can find an interval $[a,b]$ containing all the roots in polynomial time. If and only if its degree is odd, $P(a) < 0 \land P(b) > 0$, and we can locate a root between two consecutive integers by binary search.

But if $\deg(P)$ is even, what then?

Also, if $P(n)$ has an integer root, can we find it?

  • $\begingroup$ Does your conclusion "We can't multiply it out to find its coefficients" imply that you cannot evaluate the expression in polynomial time (polynomial in the length of the expression)? $\endgroup$ – hardmath Jan 6 '18 at 21:08
  • $\begingroup$ We can evaluate it in polynomial time (in terms of $\log(n)$), since we have just a finite number of multiplications and additions. But we're looking for an algorithm that runs in polynomial time in the length of the expression. $\endgroup$ – Dan Brumleve Jan 6 '18 at 21:21
  • $\begingroup$ Actually because I was missing this distinction it's not clear to me now that we can find the bounding interval $[a,b]$ in the odd-degree case. If it can't be done in polynomial time I'd still like to know how long it takes. $\endgroup$ – Dan Brumleve Jan 6 '18 at 21:26

Your Answer

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

Browse other questions tagged or ask your own question.