A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials

摘要

This work suggests a method for deriving lower bounds for the complexity of polynomials with positive real coefficients implemented by circuits of functional elements over the monotone arithmetic basis {x + y, x · y} ∪ {a · x | a ∈ ?_+}. Using this method, several new results are obtained. In particular, we construct examples of polynomials of degree m - 1 in each of the n variables with coefficients 0 and 1 having additive monotone complexity m~((1-o(1))n) and multiplicative monotone complexity m~((1/2-o(1))n) as m~n → ∞. In this form, the lower bounds derived here are sharp.