For a boolean function f : 0 1 n 0 1 , let f be the unique multilinear polynomial such that f ( x ) = f ( x ) holds for every x 0 1 n . We show that, assuming VP = VNP , there exists a polynomial-time computable f such that f requires super-polynomial arithmetic circuits. In fact, this f can be taken as a monotone 2-CNF, or a product of affine functions.

This holds over any field. In order to prove the results in characteristics two, we design new VNP-complete families in this characteristics. This includes the polynomial EC n counting edge covers in a graph, and the polynomial mclique n counting cliques in a graph with deleted perfect matching. They both correspond to polynomial-time decidable problems, a phenomenon previously encountered only in characteristics = 2 .