Monotone separations for constant degree polynomials
We prove a separation between monotone and general arithmetic formulas for polynomials of constant degree. We give an example of a polynomial C in n variables and degree k which is computable by a homogeneous arithmetic formula of size O(k(2)n(2)), but every monotone formula Computing C requires size (n/k(c))(Omega(log k))), with c is an element of (0, 1). Since the upper bound is achieved by a homogeneous arithmetic formula, we also obtain a separation between monotone and homogeneous formulas, for polynomials of constant degree. (C) 2009 Published by Elsevier B.V.
constant degree arithmetic formula computational complexity algebraic complexity arithmetic circuit