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 {n}, 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. (more…)