= Polynomial identity testing
{wiki}
Polynomial identity testing asks whether a polynomial represented implicitly, such as by an arithmetic circuit or a remainder computation, is the zero polynomial.
Here zero means that every <coefficient> vanishes after collecting equal <monomials> in the <polynomial ring>. Testing equality of two <polynomials> $A,B$ amounts to testing $P=A-B$ for zero. An <arithmetic circuit> can permit cheap <polynomial evaluation> even when expanding all <monomials> is expensive. The <random evaluation test for a polynomial identity> exploits this: one nonzero value disproves the <polynomial identity>, while a known <total degree> limits how often a nonzero <polynomial> can evade detection.<CPSC 536N: Randomized Algorithms/Lecture 9: Polynomial Identity Testing by the Schwartz-Zippel Lemma>[CPSC 536N: Randomized Algorithms; Lecture 9: Polynomial Identity Testing by the Schwartz-Zippel Lemma, §1: formal zero means all coefficients vanish; representations and evaluation access]{ref}
For example, for an <integer> $n\ge1$, $\prod_{i=1}^n(1+x_i)$ has $2^n$ distinct <monomials>, one for each <subset> of the $n$ <variables>. Its factored expression needs only $n$ <additions> and $n-1$ <multiplications> for one <polynomial evaluation>. Evaluating the compact expression avoids creating its expanded list of <coefficients>. The saving is especially attractive in many <variables>; it does not make a zero result into a proof of identity.
Back to article page
