Does there exist a polynomial-time algorithm to determine whether a given polynomial $p(n)$ with integer coefficients is positive on $\mathbb{N}$, in the sense that $p(n) \geq 0$ for all $n\in\mathbb{N}$?


[This question](https://mathoverflow.net/questions/36638/effective-algorithm-to-test-positivity) seems to be related, but it involves multivariable polynomials and asks about positivity on all of $\mathbb{R}^n$, and the answer doesn't seem to apply to single-variable polynomials.


**Edit:** Just to clarify, the input for the algorithm should be a string that encodes the polynomial $p$ in a reasonably compact fashion, e.g. the digits of the degree of $p$ followed by the digits of the coefficients.



Polynomial-time algorithm for determining whether a polynomial is positive on $\mathbb{N}$
Yes. Compute a [Sturm sequence](http://en.wikipedia.org/wiki/Sturm%27s_theorem) and use binary search to locate the real roots.


