Deterministic identity testing for arithmetic circuits
An arithmetic circuit $C$ in the variables $x_1, \dots, x_n$ is a finite directed acyclic graph with one output gate, whose input gates are labelled by variables or rational constants and whose other gates have two inputs and compute their sum or product in $\mathbb{Q}[x_1, \dots, x_n]$; a gate may feed any number of later gates. Write $f_C$ for the polynomial computed at the output. The input is an explicit encoding of $C$, with the numerators and denominators of its constants in binary, of bit length $L$, together with an integer $d \ge 1$ in unary and the promise that every gate computes a polynomial of total degree at most $d$ (the zero polynomial is allowed). No bound is placed on the depth of $C$, on the number of occurrences of a variable or on the number of monomials. Evaluation at random points (DeMillo and Lipton; Zippel; Schwartz), with the arithmetic done modulo a random prime, gives a randomized polynomial-time test. Kabanets and Impagliazzo showed that a deterministic polynomial-time test for arithmetic circuits over the integers would imply that $\mathrm{NEXP} \not\subseteq \mathrm{P/poly}$ or that the permanent has no polynomial-size arithmetic circuits. Kopparty, Saraf and Shpilka showed that deterministic factorization of polynomials given by arithmetic circuits reduces to deterministic identity testing, so that the two problems are equivalent.
Problem. Are there a deterministic Turing machine and absolute constants $K, c > 0$ such that, for every such input $(C, d)$, the machine decides whether $f_C$ is the zero polynomial of $\mathbb{Q}[x_1, \dots, x_n]$ using at most $K(L + d)^c$ bit operations?
Source: A central question of algebraic complexity; see Shpilka and Yehudayoff (2010), Chapter 4. Stated in this form (rational constants, degree bound in unary, bit complexity) by AIM — Open Applied Problems, after Kopparty, Saraf and Shpilka (2015).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- AC — Commutative Algebra
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, arithmetic circuits, derandomization, polynomial identity testing
References
@article{shpilka2010,
author = {Shpilka, Amir and Yehudayoff, Amir},
title = {Arithmetic circuits: a survey of recent results and open questions},
journal = {Found. Trends Theor. Comput. Sci.},
volume = {5},
number = {3--4},
year = {2010},
pages = {207--388},
doi = {10.1561/0400000039},
}
@article{kopparty2015,
author = {Kopparty, Swastik and Saraf, Shubhangi and Shpilka, Amir},
title = {Equivalence of polynomial identity testing and polynomial factorization},
journal = {Comput. Complexity},
volume = {24},
number = {2},
year = {2015},
pages = {295--331},
doi = {10.1007/s00037-015-0102-y},
}
@article{demillo1978,
author = {DeMillo, Richard A. and Lipton, Richard J.},
title = {A probabilistic remark on algebraic program testing},
journal = {Inform. Process. Lett.},
volume = {7},
number = {4},
year = {1978},
pages = {193--195},
doi = {10.1016/0020-0190(78)90067-4},
}
@incollection{zippel1979,
author = {Zippel, Richard},
title = {Probabilistic algorithms for sparse polynomials},
booktitle = {Symbolic and Algebraic Computation (EUROSAM '79)},
series = {Lecture Notes in Comput. Sci.},
volume = {72},
publisher = {Springer},
address = {Berlin},
year = {1979},
pages = {216--226},
doi = {10.1007/3-540-09519-5_73},
}
@article{schwartz1980,
author = {Schwartz, J. T.},
title = {Fast probabilistic algorithms for verification of polynomial identities},
journal = {J. ACM},
volume = {27},
number = {4},
year = {1980},
pages = {701--717},
doi = {10.1145/322217.322225},
}
@article{kabanets2004,
author = {Kabanets, Valentine and Impagliazzo, Russell},
title = {Derandomizing polynomial identity tests means proving circuit lower bounds},
journal = {Comput. Complexity},
volume = {13},
number = {1--2},
year = {2004},
pages = {1--46},
doi = {10.1007/s00037-004-0182-6},
}
@misc{aim-deterministic-polynomial-identity-testing,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Deterministic identity testing for arithmetic circuits}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/310-deterministic-polynomial-identity-testing.md},
note = {Entry 310 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00340, "Deterministic identity testing for arithmetic circuits", clopen.solutions.