The fundamental theorem of algebra and complexity theory

The main goal of this account is to show that a classical algorithm, Newton's method, with a standard modification, is a tractable method for finding a zero of a complex polynomial. Here, by "tractable" I mean that the cost of finding a zero doesn't grow exponentially with the degree, in a certain statistical sense. This result, our main theorem, gives some theoretical explanation of why certain "fast" methods of equation solving are indeed fast. Also this work has the effect of helping bring the discrete mathematics of complexity theory of computer science closer to classical calculus and geometry.