Polynomial identity testing

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 is one of the most important open problems in algebraic computing complexity.

Description

The question "Does equal " 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?"; in this case we can ask "Does "? 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 , where is the number of variables (here, : is the first and is the second), and is the degree of the polynomial (here, ). If and are both large, grows exponentially.[1]

PIT concerns whether a polynomial is identical to the zero polynomial, rather than whether the function implemented by the polynomial always evaluates to zero in the given domain. For example, the field with two elements, GF(2), contains only the elements 0 and 1. In GF(2), always evaluates to zero; despite this, PIT does not consider to be equal to the zero polynomial.[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]

Formal problem statement

Given an arithmetic circuit that computes a polynomial in a field, determine whether the polynomial is equal to the zero polynomial (that is, the polynomial with no nonzero terms).[1]

Solutions

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.[2]

A sparse PIT has at most nonzero monomial terms. A sparse PIT can be deterministically solved in polynomial time of the size of the circuit and the number of monomials,[1] see also.[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.[1]

gollark: It has some nice-for-users features like that you can, say, make your disk's contents unreadable if you take it out and stick it in another computer (without also having the TPM to do things to).
gollark: It's basically a bit of hardware built into the CPU for storing secret keys the user isn't meant to be able to access.
gollark: And similar accursed DRM schemes.
gollark: The older ones were low-powered in-order cores for phones and such, but now Atom-branded things go into networking appliances and are actually moderately fast.
gollark: There are lots of Atoms. They aren't actually very consistent in anything.

See also

References
  1. Saxena, Nitin. "Progress on Polynomial Identity Testing." Bulletin of the EATCS 99 (2009): 49-79.
  2. Shpilka, Amir, and Amir Yehudayoff. "Arithmetic circuits: A survey of recent results and open questions." Foundations and Trends in Theoretical Computer Science 5.3–4 (2010): 207-388.
  3. Dvir, Zeev, and Amir Shpilka. "Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits." SIAM Journal on Computing 36.5 (2007): 1404-1434.
  4. Adi Shamir. "IP=PSPACE." Journal of the ACM (JACM) 39.4 (1992): 869-877.
  5. Grigoriev,Dima, Karpinski,Marek, and Singer,Michael F., "Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields", SIAM J. Comput., Vol 19, No.6, pp. 1059-1063, December 1990
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.