TOPOLOGICAL COMPLEXITY AND SCHWARZ GENUS OF GENERAL REAL POLYNOMIAL EQUATION

We prove that the minimal number of branchings of arithmatic algorithms of approximate solution of the general real polynomial equation x(d) + a(1)x(d-1) + ... + a(d-1)x + a(d) = 0 of odd degree d grows to infinity at least as log(2) d. The same estimate is true for the c-genus of the real algebraic function associated with this equation, i.e., for the minimal number of open sets covering the space R-d of such polynomials in such a way that on ally of these sets there exists a continuous function whose value at any point (a(1), ..., a(d)), ad) is approximately (up to some sufficiently small epsilon > 0) equal to one of real roots of the corresponding equation.