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, in particular finding deterministic algorithms for PIT, is one of the most important open problems in algebraic computing complexity.

Description

The question "Does ${\displaystyle (x+y)(x-y)}$ equal ${\displaystyle x^{2}-y^{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 ${\displaystyle (x+y)(x-y)-(x^{2}-y^{2})=0}$"? 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 ${\displaystyle {\tbinom {n+d}{d}}}$, where ${\displaystyle n}$ is the number of variables (here, ${\displaystyle n=2}$: ${\displaystyle x}$ is the first and ${\displaystyle y}$ is the second), and ${\displaystyle d}$ is the degree of the polynomial (here, ${\displaystyle d=2}$). If ${\displaystyle n}$ and ${\displaystyle d}$ are both large, ${\displaystyle {\tbinom {n+d}{d}}}$ grows exponentially. ^[1]

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), ${\displaystyle x^{2}-x}$ always evaluates to zero; despite this, PIT does not consider ${\displaystyle x^{2}-x}$ to be equal to the zero polynomial. ^[2]

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". ^{[1] [3]} The study of PIT is a building-block to many other areas of computational complexity, such as the proof that IP=PSPACE. ^{[1] [4]} 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. ^[1]

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). ^[1]

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. ^[1] 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. ^[2]

A sparse PIT has at most ${\displaystyle m}$ nonzero monomial terms. A sparse PIT can be deterministically solved in polynomial time of the size of the circuit and the number ${\displaystyle m}$ of monomials, ^[1] see also. ^[5]

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. ^[1]

See also

• Applications of Schwartz–Zippel lemma

External links

• Lecture notes on "Polynomial Identity Testing by the Schwartz-Zippel Lemma"
• Polynomial Identity Testing by Michael Forbes - MIT on YouTube
• Prize winner for Polynomial Identity Testing

References

1. Saxena, Nitin. "Progress on Polynomial Identity Testing." Bulletin of the EATCS 99 (2009): 49-79.
2. Shpilka, Amir, and Amir Yehudayoff. "Arithmetic circuits: A survey of recent results and open questions." Foundations and Trends in Theoretical Computer Science 5.3–4 (2010): 207-388.
3. Dvir, Zeev, and Amir Shpilka. "Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits." SIAM Journal on Computing 36.5 (2007): 1404-1434.
4. Adi Shamir. "IP=PSPACE." Journal of the ACM (JACM) 39.4 (1992): 869-877.
5. Grigoriev, Dima, Karpinski, Marek, and Singer, Michael F., "Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields", SIAM J. Comput., Vol 19, No.6, pp. 1059-1063, December 1990