Complexity of testing for a value versus computing a function 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).
Makowski's "Algorithmic uses of the Feferman–Vaught Theorem" is possibly relevant. He defines polynomials by summing over MSOL-definable structures on graphs and shows that they are tractable to evaluate when graphs are tree-width bounded.

This doesn't say much about difference in complexity of testing/evaluation beyond being FPT. Testing for a value means asking if there exists a setting of variables such that given MSO2 formula on given graph evaluates to true, whereas evaluating involves enumerating over satisfying assignments of MSO2 formula. This seems to be related to the question of how complexity of counting SAT relates to complexity of SAT.

Edit 10/29
Another useful concept might be to look into Uniform Difficult Point Property. Apparently polynomials with this property are either easy to evaluate in all points, or hard to evaluate almost at every point. Makowski gives some references on slides 46-52 -- http://www.cs.technion.ac.il/admlogic/TR/2009/icla09-slides.pdf