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?