Deterministic polynomial identity testing

Can a computer efficiently check that an arithmetic recipe gives zero for every input, without random choices? The recipe uses integer constants built from 0 and 1, variables, and addition, subtraction and multiplication. For example, squaring ‘x plus 1’ and subtracting ‘x squared plus twice x plus 1’ always gives zero. By contrast, x times ‘x minus 1’ gives zero at 0 and 1 but gives 2 at 2. Checking a few inputs is not the same as proving an identity. The open target covers every such recipe, with running time bounded by a fixed power of its description length.[1] [2]

A compact arithmetic recipe can contain many cancellations. Can we decide, without random choices and in time polynomial in its description, whether its result is the zero polynomial? The input domain here is general integer arithmetic circuits: leaves are 0, 1 or commuting variables, and gates add, subtract or multiply earlier values.

For a small identity, name the first recipe

$$A=(x+1)^2.$$

Expanding it gives the second recipe

$$B=x^2+2x+1.$$

Their difference is $A-B=0$ for every x. In contrast, $x(x-1)$ is zero at 0 and 1, yet equals 2 at 2. The target is a formal polynomial identity, not agreement on a chosen finite sample.

Expansion need not be efficient relative to a circuit. Starting with $x+1$, s repeated squarings produce $(x+1)^{2^s}$ using s multiplication gates, while the expanded polynomial has $2^s+1$ nonzero terms. Randomized tests avoid this expansion. The unresolved question is whether arbitrary circuits admit a deterministic test with a fixed polynomial bound in their encoding size.[1]

Tests using randomness are known, but a deterministic polynomial-time test for every such circuit is not.[1] [2]

The unresolved target allows arbitrary circuit depth and repeated use of variables. Specialized formulas and fixed fan-in depth-4 results do not establish it.[1] [3] [4]

A universal test would let an algorithm certify exact algebraic equality efficiently without a chance of overlooking a nonzero expression. This matters when compact formulas hide cancellations that would be expensive to expose by fully expanding them.[1] [2]

Identity testing is also an obstacle inside other algorithms. The cited 2026 primary work connects integer PIT by efficient reductions to deciding whether certain graph pairs have equal counts of maps that preserve links, from every graph in a specified family. A general deterministic PIT algorithm would therefore remove randomness from those linked decision problems too. Alongside the known circuit-lower-bound connections, this gives the test consequences beyond checking one algebraic expression.[1] [2]