Polynomial identity testing, or PIT, is the problem of efficiently determining whether two multivariate polynomials are identical. A PIT algorithm is given an arithmetic circuit that computes a polynomial over a field and must decide whether that polynomial is the zero polynomial, a formulation equivalent to testing whether two circuits compute the same function. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Connections
In Field
Source Wikipedia: Polynomial identity testing
Uses Design Technique
Source Wikipedia: Polynomial identity testing
Sources
Wikipedia: Polynomial identity testing
Lead section
In mathematics, polynomial identity testing (PIT) is the problem of efficiently determining whether two multivariate polynomials are identical.
Uses Design Technique: Randomized Algorithms, Article body
The Schwartz-Zippel algorithm provides a practical probabilistic solution, by simply randomly testing inputs and checking whether the output is zero.
In Field: Algorithms and Complexity Theory, Lead
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.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.