<p>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 "&lt;". 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 first
time. 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$. </p>

CC BY-SA 3.0
2013-02-21T17:04:28.823Z
So the complexity of testing $f(x)=0$ is essentially captured by the complexity of *evaluating* $fg$. Then since $f$ is irreducible, the complexity of evaluating $f$ is polynomially bounded by the complexity of evaluating $fg$, the degree of $fg$, and the number of variables. So if $f$ has polynomial degree and testing $f(x)=0$ is sufficiently easy, then testing and evaluating are equivalent. (However, if either $deg f$ is large or if testing is difficult - say the degree of $g$ is very large - then this says very little.)
Joshua Grochow
CC BY-SA 3.0
2013-03-05T16:13:39.493Z
I don't get it: If you can evaluate $f$, then you can test for zero by just one more operation, namely, one equality test in the end. What could go wrong is that evaluating $fg$ is cheaper than evaluating $f$ for some reason. (Note: Evaluating $f$ means evaluating at a generic point, that is, at an indeterminate.)
Markus Bläser
CC BY-SA 3.0
2013-03-05T21:44:45.023Z
Precisely. Evaluating $fg$ might be easier than evaluating $f$. (I know that evaluating $f$ means evaluating at a generic point; I don't really understand why you thought your last parenthetical remark was necessary, but that may be besides the point.) What is it exactly that you don't get? Based on your last comment I'd say we both understand the situation and agree with one another's understanding... See also "The Complexity of Factors of Multivariate Polynomials" by Burgisser, which gives the same conclusion I stated in my previous comment.
Joshua Grochow
CC BY-SA 3.0
2013-03-05T21:46:52.900Z
Additional interesting conclusion from this discussion: although testing if the permanent of a nonnegative matrix is zero or not is easy, testing if the permanent of an arbitrary complex matrix is zero is easy if and only if evaluating the permanent is easy.
Joshua Grochow
CC BY-SA 3.0
2013-03-08T14:20:42.120Z
Sorry, I misunderstood your first comment. Everything is fine.
Markus Bläser
CC BY-SA 3.0
2011-09-26T13:51:46.177Z
2011-09-26T13:51:46.177Z
Markus Bläser
<p>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.</p>

<p>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.</p>

<p><b>Edit 10/29</b>
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 -- <a href="http://www.cs.technion.ac.il/admlogic/TR/2009/icla09-slides.pdf" rel="nofollow">http://www.cs.technion.ac.il/admlogic/TR/2009/icla09-slides.pdf</a></p>

CC BY-SA 2.5
2010-10-28T19:18:29.033Z
2010-10-29T20:35:11.010Z
2010-10-29T20:35:11.010Z
Yaroslav Bulatov
<p>I'm not sure if I understand the question correctly but let me attempt to shed some light. </p>

<p>Typically, evaluating a polynomial at certain values is easier than identity testing, especially when the representation of the polynomial is via a circuit (some succinct representation). However, there are lots of randomized identity testing algorithms (<a href="http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma" rel="nofollow">Schwarz-Zippel</a> being the most straight-forward) that works on just evaluations. </p>

<p>In certain special cases, we have 'black-box' tests for identity testing where you can test if a polynomial is zero or not by just evaluating it at a predefined set of points. A simple example of this is if the polynomial is 'sparse' (just has $n^{O(1)}$ monomials). To make the exposition simpler, lets assume the polynomial is multilinear (each monomial is a product of distinct variables). </p>

<p>A natural way to send a multivariate multilinear polynomial to a univariate is via the substitution $x_i \mapsto y^{2^i}$. The resulting polynomial is say $\sum_{i\in S} \alpha_i y^{a_i}$. This could be an exponential degree polynomial of course but let us go modulo $y^r - 1$ for a small range of $r$'s. Now an $r$ would be "bad" for a pair of monomials if $y^a$ and $y^b$ get mapped to the same monomial modulo $y^r - 1$. Or in other words, $r$ divides $a - b$. Thus as long as $r$ does not divide $\prod_{i,j\in S} (a_i - a_j)$, this wouldn't happen. Hence it is sufficient to run over a polynomial range of $r$'s. Thus, it suffices to evaluate the polynomial at some roots of unities and we can figure out of the polynomial is zero or not. </p>

<p>There has been more progress in black-box identity testing algorithms. Right now, most of then stand at restricted depth 3 circuits (sum of products of sums of variables). (FWIW) Some of this is mentioned in more details in <a href="http://www.cmi.ac.in/~ramprasad/pubs/thesis.pdf" rel="nofollow">Chapter 3 and 4 of my M.Sc thesis</a>. And there has been further improvements by <a href="http://www.math.uni-bonn.de/~saxena/papers/quad-rank-bound.pdf" rel="nofollow">Saxena and Seshadri</a> recently as well. </p>

CC BY-SA 2.5
2010-10-27T21:54:13.907Z
Unless I'm missing some connection with identity testing, I think you may have misunderstood. In addition to the fact that the polynomials are not part of the input for my question---I am rather interesting in a decision problem and a function problem defined by a family of polynomials---I am not asking about identity testing, but testing, given input $x$, whether $f(x)=0$. This is a priori easier than the general problem: given input $x$, evaluate $f(x)$. Hopefully the clarification I just added to the question makes this more clear.
Joshua Grochow
CC BY-SA 2.5
2010-10-28T05:48:23.300Z
Ah! I see... Thanks for the clarification; my answer is not too relevant in that case.
Ramprasad
CC BY-SA 2.5
2010-10-27T06:37:56.087Z
2010-10-27T06:37:56.087Z
Ramprasad
<p>I'm going to venture the idea that evaluating a polynomial $q(x)$ in $\mathbb F_p$ for fixed prime $p$ (or any finite field extension thereof, and with the coefficients restricted to the same field) will fit your criterion.</p>

<p>more concretely, lets consider a polynomial in $\mathbb F_2[x]$. We know that $x^2=x$ in $\mathbb F_2$, so if we assume that any polynomial is already in a reduced form when given as an input, we are left simply considering one of : $0,1,x,x+1$ and accordingly evaluating any of these polynomials at either of $0$ or $1$ takes at most 2 arithmetic operations.</p>

<p>I believe that a similar "constant time via fixed number of arithmetic operations" statement applies more generally for $\mathbb F_q$ where $q=p^n$ where $p$ is prime. note that if $n$ isn't fixed, this statement no longer is valid</p>

CC BY-SA 2.5
2010-08-29T05:37:25.650Z
Carter: by your reasoning, which is technically correct, the same holds true for *any* finite set of polynomials.  However, in order to be considering asymptotic complexity in any meaningful fashion, we must consider infinite families of polynomials.  This implies working either over finite fields but allowing the field (size) to vary, or working over infinite fields.  For example, when we say "the permanent" in fact we are talking about the infinite family $\{perm_{n} : n \geq 0\}$, where $perm_{n}$ is the permanent of an $n \times n$ matrix.
Joshua Grochow
CC BY-SA 2.5
2010-08-29T06:37:49.723Z
fair enough, lets clarify the question statement with "polynomials in an infinite field" rather than downvote an answer attempt that points out a needed clarification :)

your example with the permanent doesn't make this obvious, because the matrices are still over some fixed ring or field. 

Also, in the case of $\mathbb F_2$, i am not actually restricting myself to considering only those 4 polynomials, but rather using the equivalence relation of $x^2=x$ to reduce any higher degree polynomial to one of those four in time linear in the polynomial's degree.
Carter Tazio Schonwald
CC BY-SA 2.5
2010-08-29T15:30:39.253Z
Carter: I thought it was clear that I was asking about asymptotics, but I have now clarified. You could also use multivar polys where the num of vars is not fixed. Sorry for the downvote, but I don't think you deserve half the bounty (+25) for pointing out that finite sets of 1-var polys can be evaluated with O(1) ops. I know you were actually pointing out something less obvious, but that wasn't relevant to the question: *as already pointed out in the comments on the Q*, the poly is not part of the input. So over F_2 there are indeed only 4 1-var polys to consider (using x^2=x is unnecessary).
Joshua Grochow
CC BY-SA 2.5
2010-08-29T20:38:47.090Z
umm, your clarification still is broken, you need to have a fixed ring or field for the $perm_n$  stuff or its nonsense.
Carter Tazio Schonwald
CC BY-SA 2.5
2010-08-29T20:55:59.837Z
I agree with you in general, so I fixed the clarification. Interestingly, in the case of polynomials with 0,1,-1 coeffs (such as perm and det), allowing the field to vary is not total nonsense. One could imagine a result such as: "Testing whether $det_{n}$ is 0 is as hard as evaluating $det_{n}$ by over $\mathbb{F}_{p_{n}}$" (for some specified sequence $p_{n}$ of prime powers, not necessarily all of the same characteristic). Admittedly though, this wouldn't be as natural a result as over a fixed field.
Joshua Grochow
CC BY-SA 2.5
2010-08-28T21:37:11.743Z
2010-08-28T21:37:11.743Z
Carter Tazio Schonwald
<p>Any #P problem, or even #P/poly, can be written as a polynomial: make a circuit out of NAND gates, write these as $1-xy$ where $x$ and $y$ are 0-1 valued integers, and sum over all inputs. This gives a polynomial in $\mathbb{Z}[x_1,...,x_n]$ for inputs of size $n$. The decision problem is testing whether this is 0.</p>

CC BY-SA 2.5
2010-10-27T21:57:08.973Z
Yes. This is a slightly more general version of the example of the permanent. Such a decision problem is in $NP$ (or $NP/poly$). It is thought that $\# P$ is significantly harder than $NP$ (since it is as hard as the whole polynomial hierarchy).  Do you know of a general condition on $\# P$ problems that, if satisfied by a $\# P$ function $f$ implies that $f$ is no harder than its decision version?
Joshua Grochow
CC BY-SA 2.5
2010-10-28T07:38:01.903Z
There's a conjecture that the natural counting versions of NP-complete problems are always #P-complete, but I don't know any other relationship. A sort of trivial condition would be that the problem is self-reducible and f is bounded by a polynomial.
Colin McQuillan
CC BY-SA 2.5
2010-10-27T06:05:57.357Z
2010-10-27T06:05:57.357Z
Colin McQuillan
<p>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:</p>

<ul>
<li><p>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)</p></li>
<li><p>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 <a href="http://doi.acm.org/10.1145/800061.808735">Ben-Or's result</a>, since the zero set has $n$ components), but evaluating the above polynomial takes at least $\Omega(\sqrt{n})$ steps, by <a href="http://doi.ieeecomputersociety.org/10.1109/SWAT.1971.5">Paterson-Stockmeyer</a>.</p></li>
<li><p>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.</p></li>
</ul>

<blockquote>
  <p>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?</p>
</blockquote>

<p>I'm looking for conditions that do not depend on knowing the complexity of the problems beforehand.</p>

<p>(<strong>Clarification 10/27/2010</strong>) To be clear, the polynomial is not part of the input.  What that means is that, given a <em>fixed</em> family of functions $\{ f_n \}$ (one for each input size (either bitlength or number of inputs)), I want to compare the complexity of the <em>language/decision problem</em> $\{ X : f_n(X) = 0 \text{ where } n \text{ is the "size" of } X \}$ with the complexity of evaluating the <em>functions</em> $\{f_n\}$.</p>

<hr>

<p><strong>Clarification:</strong> I am asking about the <em>asymptotic</em> complexity of evaluating/testing <em>families</em> 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).</p>

CC BY-SA 2.5
2010-08-25T21:35:17.657Z
Joshua, can you 'latexize' the question for better readability ?
Suresh Venkat
CC BY-SA 2.5
2010-08-25T21:49:21.707Z
Suresh: Done.  Thanks for pointing that out.
Joshua Grochow
CC BY-SA 2.5
2010-08-27T01:34:50.613Z
One remark is that you might even ask a weaker version of this question.  Let k-PROMISE-TEST be the promise problem of testing whether the polynomial at input x equals zero or is larger than k in absolute value.  Then, when is polynomial zero-testing equivalent to solving k-PROMISE-TEST for some k>1?
arnab
CC BY-SA 2.5
2010-08-29T05:55:42.270Z
I found a paper of Valiant's (http://dx.doi.org/10.1016/0020-0190(76)90097-1) "Relative complexity of checking and evaluating", which considers essentially the same question but in the standard Turing machine setting, rather than an algebraic setting.  He doesn't answer my question, but if you found this question interesting you might also find his paper interesting.
Joshua Grochow
CC BY-SA 2.5
2010-09-02T03:25:21.153Z
I wonder if there are interesting connections to property testing here. Perhaps this question can be rephrased to test whether the polynomial is somehow "far" from 0.
Lev Reyzin
CC BY-SA 2.5
2010-10-28T03:46:04.903Z
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 easy to evaluate when graphs are tree-width bounded
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-28T05:04:08.187Z
@Yaroslav Bulatov: Very interesting! Please re-post as an answer; this is my current favorite to win the bounty, but I cannot award the bounty to a comment :).  He shows MSO-definability implies evaluation is in P, but says little about testing for a value (which could be much easier than merely being in P).  I wonder if the ideas can be extended to say something more about testing for a value...
Joshua Grochow
CC BY-SA 2.5
2010-08-17T16:25:15.770Z
Does not the anwer on your question depend not only on polynomial itself, but also on its representation?
ilyaraz
CC BY-SA 2.5
2010-08-17T18:50:10.827Z
@ilyaraz: Not sure what you mean.  The polynomial is not part of the input.
arnab
<cc.complexity-theory><reference-request><algebraic-complexity>
Complexity of testing for a value versus computing a function
Joshua Grochow
# Complexity of testing for a value versus computing a function

(Asked by: username_0 on 2010-08-17)

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).

**Tags:** cc.complexity-theory, reference-request, algebraic-complexity
> **Comments:**
> **username_5**: Does not the anwer on your question depend not only on polynomial itself, but also on its representation?  
> **username_2**: @ilyaraz: Not sure what you mean.  The polynomial is not part of the input.  
> **username_1**: Joshua, can you 'latexize' the question for better readability ?  
> **username_0**: Suresh: Done.  Thanks for pointing that out.  
> **username_2**: One remark is that you might even ask a weaker version of this question.  Let k-PROMISE-TEST be the promise problem of testing whether the polynomial at input x equals zero or is larger than k in absolute value.  Then, when is polynomial zero-testing equivalent to solving k-PROMISE-TEST for some k>1?  
> **username_0**: I found a paper of Valiant's (http://dx.doi.org/10.1016/0020-0190(76)90097-1) "Relative complexity of checking and evaluating", which considers essentially the same question but in the standard Turing machine setting, rather than an algebraic setting.  He doesn't answer my question, but if you found this question interesting you might also find his paper interesting.  
> **username_3**: I wonder if there are interesting connections to property testing here. Perhaps this question can be rephrased to test whether the polynomial is somehow "far" from 0.  
> **username_4**: 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 easy to evaluate when graphs are tree-width bounded  
> **username_0**: @Yaroslav Bulatov: Very interesting! Please re-post as an answer; this is my current favorite to win the bounty, but I cannot award the bounty to a comment :).  He shows MSO-definability implies evaluation is in P, but says little about testing for a value (which could be much easier than merely being in P).  I wonder if the ideas can be extended to say something more about testing for a value...  

---

## 5 answers

### Answer by username_6 on 2011-09-26. Score: 4 | Accepted answer

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 first
time. 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$.

> **Comments:**
> **username_0**: So the complexity of testing $f(x)=0$ is essentially captured by the complexity of *evaluating* $fg$. Then since $f$ is irreducible, the complexity of evaluating $f$ is polynomially bounded by the complexity of evaluating $fg$, the degree of $fg$, and the number of variables. So if $f$ has polynomial degree and testing $f(x)=0$ is sufficiently easy, then testing and evaluating are equivalent. (However, if either $deg f$ is large or if testing is difficult - say the degree of $g$ is very large - then this says very little.)  
> **username_6**: I don't get it: If you can evaluate $f$, then you can test for zero by just one more operation, namely, one equality test in the end. What could go wrong is that evaluating $fg$ is cheaper than evaluating $f$ for some reason. (Note: Evaluating $f$ means evaluating at a generic point, that is, at an indeterminate.)  
> **username_0**: Precisely. Evaluating $fg$ might be easier than evaluating $f$. (I know that evaluating $f$ means evaluating at a generic point; I don't really understand why you thought your last parenthetical remark was necessary, but that may be besides the point.) What is it exactly that you don't get? Based on your last comment I'd say we both understand the situation and agree with one another's understanding... See also "The Complexity of Factors of Multivariate Polynomials" by Burgisser, which gives the same conclusion I stated in my previous comment.  
> **username_0**: Additional interesting conclusion from this discussion: although testing if the permanent of a nonnegative matrix is zero or not is easy, testing if the permanent of an arbitrary complex matrix is zero is easy if and only if evaluating the permanent is easy.  
> **username_6**: Sorry, I misunderstood your first comment. Everything is fine.  

---

### Answer by username_4 on 2010-10-28. Score: 6

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>


---

### Answer by username_7 on 2010-10-27. Score: 3

I'm not sure if I understand the question correctly but let me attempt to shed some light.

Typically, evaluating a polynomial at certain values is easier than identity testing, especially when the representation of the polynomial is via a circuit (some succinct representation). However, there are lots of randomized identity testing algorithms ([Schwarz-Zippel](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma) being the most straight-forward) that works on just evaluations.

In certain special cases, we have 'black-box' tests for identity testing where you can test if a polynomial is zero or not by just evaluating it at a predefined set of points. A simple example of this is if the polynomial is 'sparse' (just has $n^{O(1)}$ monomials). To make the exposition simpler, lets assume the polynomial is multilinear (each monomial is a product of distinct variables).

A natural way to send a multivariate multilinear polynomial to a univariate is via the substitution $x\_i \mapsto y^{2^i}$. The resulting polynomial is say $\sum\_{i\in S} \alpha\_i y^{a\_i}$. This could be an exponential degree polynomial of course but let us go modulo $y^r - 1$ for a small range of $r$'s. Now an $r$ would be "bad" for a pair of monomials if $y^a$ and $y^b$ get mapped to the same monomial modulo $y^r - 1$. Or in other words, $r$ divides $a - b$. Thus as long as $r$ does not divide $\prod\_{i,j\in S} (a\_i - a\_j)$, this wouldn't happen. Hence it is sufficient to run over a polynomial range of $r$'s. Thus, it suffices to evaluate the polynomial at some roots of unities and we can figure out of the polynomial is zero or not.

There has been more progress in black-box identity testing algorithms. Right now, most of then stand at restricted depth 3 circuits (sum of products of sums of variables). (FWIW) Some of this is mentioned in more details in [Chapter 3 and 4 of my M.Sc thesis](http://www.cmi.ac.in/~ramprasad/pubs/thesis.pdf). And there has been further improvements by [Saxena and Seshadri](http://www.math.uni-bonn.de/~saxena/papers/quad-rank-bound.pdf) recently as well.

> **Comments:**
> **username_0**: Unless I'm missing some connection with identity testing, I think you may have misunderstood. In addition to the fact that the polynomials are not part of the input for my question---I am rather interesting in a decision problem and a function problem defined by a family of polynomials---I am not asking about identity testing, but testing, given input $x$, whether $f(x)=0$. This is a priori easier than the general problem: given input $x$, evaluate $f(x)$. Hopefully the clarification I just added to the question makes this more clear.  
> **username_7**: Ah! I see... Thanks for the clarification; my answer is not too relevant in that case.  

---

### Answer by username_8 on 2010-08-28. Score: 3

I'm going to venture the idea that evaluating a polynomial $q(x)$ in $\mathbb F\_p$ for fixed prime $p$ (or any finite field extension thereof, and with the coefficients restricted to the same field) will fit your criterion.

more concretely, lets consider a polynomial in $\mathbb F\_2[x]$. We know that $x^2=x$ in $\mathbb F\_2$, so if we assume that any polynomial is already in a reduced form when given as an input, we are left simply considering one of : $0,1,x,x+1$ and accordingly evaluating any of these polynomials at either of $0$ or $1$ takes at most 2 arithmetic operations.

I believe that a similar "constant time via fixed number of arithmetic operations" statement applies more generally for $\mathbb F\_q$ where $q=p^n$ where $p$ is prime. note that if $n$ isn't fixed, this statement no longer is valid

> **Comments:**
> **username_0**: Carter: by your reasoning, which is technically correct, the same holds true for *any* finite set of polynomials.  However, in order to be considering asymptotic complexity in any meaningful fashion, we must consider infinite families of polynomials.  This implies working either over finite fields but allowing the field (size) to vary, or working over infinite fields.  For example, when we say "the permanent" in fact we are talking about the infinite family $\{perm_{n} : n \geq 0\}$, where $perm_{n}$ is the permanent of an $n \times n$ matrix.  
> **username_8**: fair enough, lets clarify the question statement with "polynomials in an infinite field" rather than downvote an answer attempt that points out a needed clarification :)  your example with the permanent doesn't make this obvious, because the matrices are still over some fixed ring or field.   Also, in the case of $\mathbb F_2$, i am not actually restricting myself to considering only those 4 polynomials, but rather using the equivalence relation of $x^2=x$ to reduce any higher degree polynomial to one of those four in time linear in the polynomial's degree.  
> **username_0**: Carter: I thought it was clear that I was asking about asymptotics, but I have now clarified. You could also use multivar polys where the num of vars is not fixed. Sorry for the downvote, but I don't think you deserve half the bounty (+25) for pointing out that finite sets of 1-var polys can be evaluated with O(1) ops. I know you were actually pointing out something less obvious, but that wasn't relevant to the question: *as already pointed out in the comments on the Q*, the poly is not part of the input. So over F_2 there are indeed only 4 1-var polys to consider (using x^2=x is unnecessary).  
> **username_8**: umm, your clarification still is broken, you need to have a fixed ring or field for the $perm_n$  stuff or its nonsense.  
> **username_0**: I agree with you in general, so I fixed the clarification. Interestingly, in the case of polynomials with 0,1,-1 coeffs (such as perm and det), allowing the field to vary is not total nonsense. One could imagine a result such as: "Testing whether $det_{n}$ is 0 is as hard as evaluating $det_{n}$ by over $\mathbb{F}_{p_{n}}$" (for some specified sequence $p_{n}$ of prime powers, not necessarily all of the same characteristic). Admittedly though, this wouldn't be as natural a result as over a fixed field.  

---

### Answer by username_9 on 2010-10-27. Score: 1

Any #P problem, or even #P/poly, can be written as a polynomial: make a circuit out of NAND gates, write these as $1-xy$ where $x$ and $y$ are 0-1 valued integers, and sum over all inputs. This gives a polynomial in $\mathbb{Z}[x\_1,...,x\_n]$ for inputs of size $n$. The decision problem is testing whether this is 0.

> **Comments:**
> **username_0**: Yes. This is a slightly more general version of the example of the permanent. Such a decision problem is in $NP$ (or $NP/poly$). It is thought that $\# P$ is significantly harder than $NP$ (since it is as hard as the whole polynomial hierarchy).  Do you know of a general condition on $\# P$ problems that, if satisfied by a $\# P$ function $f$ implies that $f$ is no harder than its decision version?  
> **username_9**: There's a conjecture that the natural counting versions of NP-complete problems are always #P-complete, but I don't know any other relationship. A sort of trivial condition would be that the problem is self-reducible and f is bounded by a polynomial.  

---

