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.
" 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?
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
[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] 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.
nonzero monomial terms.
A sparse PIT can be deterministically solved in polynomial time of the size of the circuit and the number
[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.