Abstract
A monotone arithmetic circuit computes a given multivariate polynomial f if its values on all nonnegative integer inputs are the same as those of f. The circuit counts f if this holds for 0-1 inputs; on other inputs, the circuit may output arbitrary values. The circuit decides f if it has the same 0-1 roots as f. We first show that some multilinear polynomials can be exponentially easier to count than to compute them, and that some polynomials can be exponentially easier to decide than to count them. Our main results are general lower bounds on the size of counting circuits.