A basic instance of algebraic identity testing is the Arithmetic Circuit Identity Testing (ACIT) problem, which involves deciding the zeroness of an integer represented as an arithmetic circuit. The difficulty in this problem is that the integer may have bit-length exponential in the size of the circuit. However, the problem admits a randomized polynomial-time algorithm: one evaluates the circuit modulo a prime that is randomly chosen in a certain range. The ACIT problem turns out to be polynomial-time interreducible with the problem of determining zeroness of an arithmetic circuit evaluated in the ring of multivariate polynomials: the so-called Polynomial Identity Testing (PIT) problem [1]}.
Over the years, PIT has found diverse applications in algorithm design; a few well-known examples are program testing [2]}, detecting perfect matchings [3]}, factoring polynomials [4]}, pattern matching in compressed texts [5]}, [6]}, primality testing [7]}, [8]}, equivalence and minimization of weighted automata [9]}, [10]} and linear recurrence sequences [11]}, [12]}.
Whether PIT admits a deterministic polynomial-time algorithm is one of the central open questions in complexity theory.
