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 μ, we show that the problem of determining all roots of p with error less than 2-μ is in the parallel complexity class NC. To do this, we construct an algorithm which runs on at most D(n + m + μ)f processors in at most C loge(n + m - μ) parallel steps, where the constants C, D, e, f are given in terms of the corresponding processor and time bounds for the computation of certain elementary polynomial and matrix operations. In fact, one can easily see that the time complexity is O(log3(n + m + μ)). Thus, the algorithm presented here extends the algorithm of Ben-Or, Feig, Kozen, and Tiwari by removing the severe restriction that all the roots of p(z) be real. © 1994 Academic Press, Inc. All rights reserved.