Polynomial complexity algorithms for computational problems in the theory of algebraic curves

It is proved that the classical algorithm for constructing Newton-Puiseux expansions for the roots of polynomials using the method of Newton polygons is of polynomial complexity in the notation length of the expansion coefficients. This result is used, in the case of a ground field of characteristic O, to construct polynomial-time algorithms for factoring polynomials over fields of formal power series, and for fundamental computational problems in the theory of algebraic curves, such as curve normalization.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 176, pp. 127–150, 1989.