Polynomial-time algorithms for computational problems in the theory of algebraic curves

A. L. Chistov

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 4, Tome 176 (1989), pp. 127-150

Résumé

It is proved that the classical algorithm for computing the Newton–Puiseux expansion of roots of a polynomial using the Newton polygon's method has a polynomial complexity in the model of computation when sizes of coefficients and constant fields are taking into account. As a consequence we get polynomial-time algorithms for factoring polynomials over fields of zero characteristic of formal power series in one variable. Further, there are constructed polynomial-time algorithms for computing uniformizing elements of local rings of points of algebraic curves, indices of ramification and inertia, the geometrical genus of a curve, the normalization of an algebraic curve. By definition we set that a series is computed in time polynomial in $A_1,\dots,A_m$ iff for each $i$ its $i$-th partial sum is computed in time polynomial in $A_1,\dots,A_m$ and $i$. The estimation of length of coefficients of the Newton-Peuiseux expansion is central in the paper. It is based mainly on the lemma 2.1 which affords to reduce the general problem to the some analog of Hensel's lifting with only one step in the Newton–Peiseux expansion till the stabilization, i.e. separation of roots of the polynomial in the Newton polygon.