Polynomial identity testing

Fix a field $F$ and a representation of multivariate polynomials over $F[x_1,\dots ,x_m]$ for which:

• the number of variables $m$ and a total-degree bound $d$ can be computed in polynomial time from the input representation, and
• evaluation at any chosen point of $F^m$ can be performed in polynomial time.

The corresponding polynomial identity testing problem (PIT) asks whether a given represented polynomial is the zero polynomial of Polynomial rings in finitely many commuting indeterminates by iteration, with total degree understood as in Monomials, coefficients, degree in each variable and total degree in $F[x_1,\dots ,x_n]$.

• The input is a representation of a polynomial, not its full value table.
• The later coRP classification uses random evaluation together with an explicit finite sample set whose size dominates the degree bound.