Math Conjectures

Deterministic Polynomial Identity Testing

OPENLandmarkOpen problemProposed c. 1980 · Standard version

Canonical statement

Is there a deterministic polynomial-time algorithm which, given a division-free arithmetic circuit over Q\mathbb Q with binary-encoded rational constants, decides whether the formal polynomial computed by the circuit is identically zero, in time polynomial in the circuit's binary encoding length?
View source LaTeX
Is there a deterministic polynomial-time algorithm which,
given a division-free arithmetic circuit over \(\mathbb Q\) with
binary-encoded rational constants, decides whether the formal polynomial
computed by the circuit is identically zero, in time polynomial in the
circuit's binary encoding length?
TCS-024:[Schwartz1980PIT][KabanetsImpagliazzo2004][ShpilkaYehudayoff2010]
Theoretical computer scienceAlgebra and representation theory

Notes

Polynomial identity testing asks for a deterministic polynomial-time algorithm that decides whether a given division-free arithmetic circuit over Q\mathbb Q computes the identically zero polynomial. The modern formulation dates from around 1980, when Schwartz showed that evaluating the circuit at random points detects a nonzero polynomial with high probability, giving a simple randomized polynomial-time algorithm [Schwartz1980PIT]; the open question is whether the randomness can be removed.

The problem is a flagship instance of derandomization. Deterministic algorithms are known for various restricted circuit classes, as surveyed by Shpilka and Yehudayoff [ShpilkaYehudayoff2010], and Kabanets and Impagliazzo showed that the difficulty is no accident: derandomizing identity testing in general would imply major arithmetic-circuit lower bounds [KabanetsImpagliazzo2004], so progress is tightly linked to the hardest questions about explicit circuits.

The general case is open: a resolution requires an unconditional deterministic polynomial-time test — which would carry lower bounds with it — or an explanation of why none exists.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.