← All Problems
Open

Polynomial Root Approximation (PRA)

Category: Formal Languages

Input

An $n^\text{th}$ degree polynomial $p \in \Z[x]$, and an integer $\mu$.

Problem

For each (real or complex) root $z_i$, $1 \leq i \leq n$, of $p$, an approximation $\tilde{z}_i$ such that $|z_i - \tilde{z}_i| < 2^{-\mu}$.

Status

Open (Ben-Or et al. [1]).

Remarks

If all the roots are real, the problem is in $\NC$ [1].

References

  1. M. Ben-Or, E. Feig, D. C. Kozen, and P. Tiwari (1988). A fast parallel algorithm for determining all roots of a polynomial with real roots.
  2. Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem B.7.3.