Bürgisser, Peter(D-BONN-I5); Lickteig, Thomas(D-BONN-I5); Shub, Michael(1-IBM-M)

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.