36
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ Does not the anwer on your question depend not only on polynomial itself, but also on its representation? $\endgroup$
    – ilyaraz
    Aug 17, 2010 at 16:25
  • $\begingroup$ @ilyaraz: Not sure what you mean. The polynomial is not part of the input. $\endgroup$
    – arnab
    Aug 17, 2010 at 18:50
  • $\begingroup$ Joshua, can you 'latexize' the question for better readability ? $\endgroup$ Aug 25, 2010 at 21:35
  • 4
    $\begingroup$ I found a paper of Valiant's (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. $\endgroup$ Aug 29, 2010 at 5:55
  • 1
    $\begingroup$ 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 $\endgroup$ Oct 28, 2010 at 3:46

5 Answers 5

4
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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.) $\endgroup$ Feb 21, 2013 at 17:04
  • $\begingroup$ 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.) $\endgroup$ Mar 5, 2013 at 16:13
  • $\begingroup$ 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. $\endgroup$ Mar 5, 2013 at 21:44
  • $\begingroup$ 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. $\endgroup$ Mar 5, 2013 at 21:46
  • $\begingroup$ Sorry, I misunderstood your first comment. Everything is fine. $\endgroup$ Mar 8, 2013 at 14:20
6
+50
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 29, 2010 at 5:37
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 29, 2010 at 6:37
  • 1
    $\begingroup$ 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). $\endgroup$ Aug 29, 2010 at 15:30
  • $\begingroup$ umm, your clarification still is broken, you need to have a fixed ring or field for the $perm_n$ stuff or its nonsense. $\endgroup$ Aug 29, 2010 at 20:38
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 29, 2010 at 20:55
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Oct 27, 2010 at 21:54
  • $\begingroup$ Ah! I see... Thanks for the clarification; my answer is not too relevant in that case. $\endgroup$
    – Ramprasad
    Oct 28, 2010 at 5:48
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Oct 27, 2010 at 21:57
  • $\begingroup$ 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. $\endgroup$ Oct 28, 2010 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.