In general we know that the complexity of testing whether a function takes a particular value at a given input is easier than evaluating the function at that input.  For example:Evaluating the permanent of a nonnegative integer matrix is #P-hard, yet telling whether such a permanent is zero or nonzero is in P (bipartite matching)There are n real numbers $a_1,...,a_n$, such that the polynomial $\prod_{i=1}^{n}(x - a_i)$ has the following properties (indeed most sets of $n$ real numbers will have these properties). For given input $x$, testing whether or not this polynomial is zero takes $\Theta(\log n)$ multiplications and comparisons (by Ben-Or's result, since the zero set has $n$ components), but evaluating the above polynomial takes at least $\Omega(\sqrt{n})$ steps, by Paterson-Stockmeyer.Sorting requires $\Omega(n \log n)$ steps on a comparison tree (also $\Omega(n \log n)$ steps on a real algebraic decision tree, again by Ben-Or's result), but testing if a list is sorted only uses $n-1$ comparisons.Are there general conditions on a polynomial that are sufficient to imply that the (algebraic) complexity of testing whether or not the polynomial is zero is equivalent to the complexity of evaluating the polynomial?I'm looking for conditions that do not depend on knowing the complexity of the problems beforehand.(Clarification 10/27/2010) To be clear, the polynomial is not part of the input.  What that means is that, given a fixed family of functions $\{ f_n \}$ (one for each input size (either bitlength or number of inputs)), I want to compare the complexity of the language/decision problem $\{ X : f_n(X) = 0 \text{ where } n \text{ is the size of } X \}$ with the complexity of evaluating the functions $\{f_n\}$.Clarification: I am asking about the asymptotic complexity of evaluating/testing families of polynomials.  For example, over a fixed field (or ring, such as $\mathbb{Z}$) the permanent is not a single polynomial, but an infinite family $\{perm_{n} : n \geq 0 \}$ where $perm_{n}$ is the permanent of an $n \times n$ matrix over that field (or ring).
Complexity of testing for a value versus computing a function
cc.complexity theory;reference request;algebraic complexity
Over $\mathbb{C}$, testing for zero and evaluation is almost the same in the following sense: Assume you have a decision tree which tests whether some irreducible polynomial $f$ is nonzero.We are working over $\mathbb{C}$, therefore we can only test for equality but we do not have <. That is the important difference to the second example in the question!Now take the typical path, i.e., the path taken by almost all inputs (we always follow the $\not=$-branch). Furthermore, take the typical path of all elements in the variety $V(f)$. Let $v$ be the node at which these two paths take a different branch for the firsttime. Let $h_1,\dots,h_m$ be the polynomials that are tested along the common prefix of the two path. Since $V(f)$ is closed, all elements that lie in $V(f)$ and reach $v$ also lie in $V(h_m)$. Therefore, if $f(x) = 0$, then one of the $h_i$ vanishes on $x$. We apply Hilbert's Nullstellensatz to $h_1 \cdots h_m$ and get that $f g = h_1 \cdots h_m$ for some polynomial $g$ that's coprime to $f$. In short, while we are not computing $f$, when deciding whether $f(x) = 0$, we have to compute $fg$ for some coprime $g$. 