93j:68070 68Q25
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

Back