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](http://doi.acm.org/10.1145/800061.808735), since the zero set has $n$ components), but evaluating the above polynomial takes at least $\Omega(\sqrt{n})$ steps, by [Paterson-Stockmeyer](http://doi.ieeecomputersociety.org/10.1109/SWAT.1971.5).
* 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).