Specified precision polynomial root isolation is in NC
C. Andrew Neff · 2002
Given a polynomial p(z) od degree n with integer coefficients, whose absolute values are bounded above by 2/sup m/, and a specified integer mu , it is shown that the problem of determining all roots of p with error less than 2/sup - mu / is in the parallel complexity class NC. To do this, an algorithm that runs on at most POLY(n+m+ mu ) processors with a parallel time complexity of O(log/sup 3/(n+m+ mu )) is constructed. This algorithm extends the algorithm of M. Ben-Or et al. (SIAM J. Comput., vol.17, p.1081-92, 1988) by removing the severe restriction that all the roots of p(z) should be real. >