Specified precision polynomial root isolation is in NC

Abstract

Given a polynomial p(z) of degree n with integer coefficients, whose absolute values are bounded above by 2m, and a specified integer μ, it is shown that the problem of determining all roots of p with error less than 2-μ is in the parallel complexity class NC. To do this, an algorithm that runs on at most POLY (n + m + μ) processors with a parallel time complexity of O(log3(n + m + μ)) is constructed. This algorithm extends the algorithm of M. Ben-Or et al. (SIAM J. Comput., Vol. 17, pp. 1081-1092, 1988) by removing the severe restriction that all the roots of p(z) be real.