The Arithmetic Circuit Combinatorial Nullstellensatz is NP-hard

Andreas Björklund

A multivariate polynomial on $n$ variables $x_1,\dots ,x_n$ of total degree $n$ over ${\mathbf{Z}}_2$ containing the multilinear monomial ${\prod }_{i=1}^n{x}_i$ is by the combinatorial…