Complexity of testing for a value versus computing a function

Question

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

Answer 1

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

Answer 2

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

Answer 4

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 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. And there has been further improvements by Saxena and Seshadri recently as well.

Answer 5

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.