The Arithmetic Circuit Combinatorial Nullstellensatz is NP-hard

Abstract

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 nullstellensatz [Alon, Comb. Probab. Comput., 1999] known to always have a nonroot. We show that there cannot be a randomised polynomial time algorithm that given an arithmetic circuit of polynomial size formally computing such a polynomial, locates a nonroot with constant nonzero probability unless RP=NP. The result holds even when the individual degree of every variable in the input polynomial is at most two.