Polynomial identity testing

In mathematics, polynomial identity testing (PIT) is the problem of efficiently determining whether two multivariate polynomials are identical. More formally, a PIT algorithm is given an arithmetic circuit that computes a polynomial p in a field, and decides whether p is the zero polynomial. Determining the computational complexity required for polynomial identity testing is one of the most important open problems in algebraic computing complexity.
Description.
The question "Does formula_1 equal formula_2" is a question about whether two polynomials are identical. As with any polynomial identity testing question, it can be trivially transformed into the question "Is a certain polynomial equal to 0?"; in this case we can ask "Does formula_3"? If we are given the polynomial as an algebraic expression (rather than as a black-box), we can confirm that the equality holds through brute-force multiplication and addition, but the time complexity of the brute-force approach grows as formula_4, where formula_5 is the number of variables (here, formula_6: formula_7 is the first and formula_8 is the second), and formula_9 is the degree of the polynomial (here, formula_10). If formula_5 and formula_9 are both large, formula_4 grows exponentially.
PIT concerns whether a polynomial is identical to the zero polynomial, rather than whether the function implemented by the polynomial always evaluates to zero in the given domain. For example, the field with two elements, GF(2), contains only the elements 0 and 1. In GF(2), formula_14 always evaluates to zero; despite this, PIT does not consider formula_14 to be equal to the zero polynomial.
Determining the computational complexity required for polynomial identity testing is one of the most important open problems in the mathematical subfield known as "algebraic computing complexity". The study of PIT is a building-block to many other areas of computational complexity, such as the proof that IP=PSPACE. In addition, PIT has applications to Tutte matrices and also to primality testing, where PIT techniques led to the AKS primality test, the first deterministic (though impractical) polynomial time algorithm for primality testing.
Formal problem statement.
Given an arithmetic circuit that computes a polynomial in a field, determine whether the polynomial is equal to the zero polynomial (that is, the polynomial with no nonzero terms).
Solutions.
In some cases, the specification of the arithmetic circuit is not given to the PIT solver, and the PIT solver can only input values into a "black box" that implements the circuit, and then analyze the output. Note that the solutions below assume that any operation (such as multiplication) in the given field takes constant time; further, all black-box algorithms below assume the size of the field is larger than the degree of the polynomial.
The Schwartz–Zippel algorithm provides a practical probabilistic solution, by simply randomly testing inputs and checking whether the output is zero. It was the first randomized polynomial time PIT algorithm to be proven correct. The larger the domain the inputs are drawn from, the less likely Schwartz–Zippel is to fail. If random bits are in short supply, the Chen-Kao algorithm (over the rationals) or the Lewin-Vadhan algorithm (over any field) require fewer random bits at the cost of more required runtime.
A "sparse PIT" has at most formula_16 nonzero monomial terms. A sparse PIT can be deterministically solved in polynomial time of the size of the circuit and the number formula_16 of monomials, see also.
A "low degree PIT" has an upper bound on the degree of the polynomial. Any low degree PIT problem can be reduced in subexponential time of the size of the circuit to a PIT problem for depth-four circuits; therefore, PIT for circuits of depth-four (and below) is intensely studied. 