Bürgisser, Peter(D-BONN-I5); Lickteig, Thomas(D-BONN-I5); Shub, Michael(1-IBM-M)
Test complexity of generic polynomials.
(English. English summary)
J. Complexity 8 (1992), no. 3, 203--215.
Given a polynomial $f\colon\bold C\sp m\to\bold C$, we can consider two
problems: (1) evaluating $f$; (2) checking if $f(\xi)=0$ by evaluating
$f$ at $\xi$. Obviously, (2) can be dealt with by doing (1). From the
viewpoint of complexity, (2) seems to be easier than (1). However,
this paper indicates that if $f$ is sufficiently general, the
complexity for both cases (1) and (2) is almost the same.
© Copyright American Mathematical Society 1993, 1997