Polynomial Identity Testing (PIT) is a problem in computer science and computational algebra that involves determining whether a given polynomial is identically zero. In other words, given a polynomial \( P(x_1, x_2, \ldots, x_n) \) expressed in some algebraic form, the task is to decide if \( P(x_1, x_2, \ldots, x_n) = 0 \) for all possible values of its variables.
Articles by others on the same topic
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 amounts to testing 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.[ref]
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
For example, for an integer , has distinct monomials, one for each subset of the variables. Its factored expression needs only additions and 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.