Additive Complexity and Zeros of Real Polynomials
Jean-Jacques Risler · SIAM Journal on Computing · 1985
Let $P \in R[ X ]$ be a polynomial of additive complexity k (the additive complexity is the minimal number of $ \pm $ operations needed to compute P over R). It is shown that there exists a constant C (independent of P) such that the number of distinct real zeros of P is $ \leqq C^{k^2 } $. This is an improvement on a result of Borodin and Cook (SIAM J. Comput., 5 (1970), pp. 146–157). This result is then generalized to polynomials in several variables, the number of zeros being replaced by the number of connected components of the zero set.