Oftentimes, we might want to test that two polynomials are equal. Many problems can be encoded as the equality of two polynomials—as we are going to see later, the existence of a bipartite matching in a graph can be phrased by saying that a certain determinant polynomial is nonzero.
1. Polynomials
Testing that a polynomial in the usual encoding (as a list of coefficients) is nontrivial is, of course, a trivial task, one that a simple linear scan would accomplish. But, as we are going to see, the polynomials that one may wish to test for being nonzero need not be presented to us in this form. Rather, they may come to us recursively.
Here is one example. We can think of a boolean formula as a tree of gates. Each gate has one or two ends flowing into it and one edge leaving. The gates can be and, or, and not (in the last case, one edge flows in). Given the boolean inputs that flow into it, the gate outputs true or false according to the usual formulas. Finally, there are input gates where one can choose to place either true or false, and one final output gate at the end. We can connect the output lines of gates as input lines of new gates, and combining them, we can get a boolean formula.
Similarly, we could present a polynomial as a tree of gates. Each gate is either addition or multiplication; the input gates can hold variables or constants. When we put the inputs in, we get a polynomial. But in a gate of size , the total output (because of all the multiplications) could be exponential in the degree! The upshot of this is that, if we are presented with a polynomial in the form of a tree of gates, we find that actually evaluating the coefficients of the polynomial may be an exponential-time, intractable task. But if we wanted to evaluate the polynomial at a specific value, and modulo some (not too large) value, we could do it efficiently, by working through the gates and reducing mod the value at each step to keep things from getting too large.
So we get the idea that to test whether a polynomial is nonzero, it may be useful, instead of expanding it out, to evaluate it on some specific values, in which case we will get a probabilistic algorithm. However, nonzero polynomials have roots, and to make such an approach of testing work, we will have to randomize things.
2. The Schwarz-Zippel lemma
The Schwarz-Zippel lemma gives a bound on the probability that a multivariate polynomial over a finite field will have roots in a given set.
Lemma 1 (Schwarz-Zippel) Let
be a field,
a nonzero polynomial of total degree
. Suppose
is a finite subset. Then if the tuple
is randomly chosen from
, then the probability that
is at most
.
We are going to prove this by induction on the number of variables. When
, this is just the statement that a one-variable polynomial of degree
can have at most
roots (if it is nonzero). Now suppose the result proved for
. We can write
where involves only the first
variables and has degree
. Let
be the largest index such that
is not identically zero. Then at the pairs
such that
, there will be at most
choices of
to make
vanish. So we have
By induction, this is at most
which proves the lemma.
3. Polynomial identity testing
So, we are given the following situation. We have two polynomials expressed in some funny form (like via an arithmetic circuit), and these polynomials may have very large degree (exponential in the input size
). However, if
is a reasonable number (of size polynomial in
), we can evaluate the polynomials
mod
in polynomial time. This is the case for the boolean circuit, for instance.
Then actually computing the coefficients cannot be done efficiently because the degree is exponential. Even computing the value of
by themselves is infeasible because the output may need exponentially many bits! However, we can compute their values mod any small
. From this, we want a probabilistic algorithm that will tell us whether
or not.
Here is the idea. Let us suppose we know that the degrees of are at most
(which is generally exponential in
). Given this, choose
randomly in
. (Then
has
bits, so we are ok.) Choose inputs
randomly in
. Then we evaluate
mod
on
. This can be done in polynomial time. If this is zero, output that
are equal; if not, output that they are unequal.
What we need to show is that if , then there is a high probability that the algorithm will output “unequal.” Well, there is a high probability that
as integers by the Schwarz-Zippel lemma. Suppose that these two values are indeed unequal; then the claim is that for most choices of
, we will get something nonzero mod
. But
is
, so it has
prime factors. Conversely, there are about
possible primes in
. So the probability that
is prime and does not divide
is at least
which is comparable to or comparable to
. It follows that the probability that our algorithm falsely concludes that two unequal polynomials are equal is about
. Granted, this is
as
. So, to make it better, we just run it
times or so; then the probability that our algorithm fails is small, while it still runs in polynomial time.
I should probably mention that I’m drawing the material from these computer science posts primarily from Papadimitriou’s and Arora-Barak’s textbooks on complexity theory, and some of my (limited) understanding of basic algorithms comes from CLRS (as well as the course I am taking).
Leave a Reply