Strongly Exponential Separation between Monotone VP and Monotone VNP

摘要

We show that there is a sequence of explicit multilinear polynomials P_n(x_1,...,x_n) ∈ R[x_1,... ,x_n] with non-negative coefficients that lies in monotone VNP such that any monotone algebraic circuit for P_n must have size exp(Ω(n)). This builds on (and strengthens) a result of Yehudayoff (STOC 2019) who showed a lower bound of exp(Ω(n~ (1/2)).