Strongly Exponential Separation Between Monotone VP and Monotone VNP

摘要

We show that there is a sequence of explicit multilinear polynomials Pn(x1, . . . , xn) ∈R[x1, . . . , xn] with non-negative coefficients that lies in monotone VNP such that any monotonealgebraic circuit for Pn must have size exp(?(n)). This builds on (and strengthens) a resultof Yehudayoff (2018) who showed a lower bound of exp(?( ?√n)).