LIMITING NEGATIONS IN CONSTANT DEPTH CIRCUITS

It follows from a theorem of Markov that the minimum number of negation gates in a circuit sufficient to compute any Boolean function on n variables is l = right perpendicular log n left perpendicular + 1. It can be shown that, for functions computed by families of polynomial size, O(log n) depth and bounded fan-in circuits (NC1), the same result holds: on such circuits l negations are necessary and sufficient. In this paper it is proven that this situation changes when polynomial size circuit families of constant depth are considered: l negations are no longer sufficient. For threshold circuits it is proven that there are Boolean functions computable in constant depth (TC0) such that no such threshold circuit containing o(n(epsilon)), for all epsilon > 0, negations can compute them. There is a matching upper bound: for any epsilon > 0, everything computable by constant depth threshold circuits can be computed by constant depth threshold circuits using n(epsilon) negations asymptotically. There are also tight bounds for constant depth, unbounded fan-in circuits (AC0): n/log(r) n, for any r, negations are sufficient, and OMEGA(n/ log(r) n), for some r, are necessary.