## Polynomial size constant depth circuits with a limited number of negations.(English)Zbl 0764.94025

Theoretical aspects of computer science, Proc. 8th Annu. Symp., STACS ’91, Hamburg/Ger. 1991, Lect. Notes Comput. Sci. 480, 228-237 (1991).
Summary: [For the entire collection see Zbl 0753.00019.]
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=\lfloor\log n\rfloor+1$$. It can be shown that, for functions computed by families of polynomial size, $$O(\log n)$$ depth and bounded fan-in circuits $$(NC^ 1)$$, the same result holds: on such circuits $$l$$ negations are necessary and sufficient. In this paper we prove that this situation changes when polynomial size circuit families of constant depth are considered: $$l$$ negations are no longer sufficient. For threshold circuits we prove that there are Boolean functions computable in constant depth $$(TC^ 0)$$ such that no such threshold circuit containing $$o(n^ \varepsilon)$$, for all $$\varepsilon>0$$, negations can compute them. We have a matching upper bound: for any $$\varepsilon>0$$, everything computed by constant depth threshold circuits can be so computed using $$n^ \varepsilon$$ negations asymptotically. We also have tight bounds for constant depth, unbounded fan-in circuits $$(AC^ 0): n/\log^ r n$$, for any $$r$$, negations are sufficient, and $$\Omega(n/\log^ r n)$$, for some $$r$$, are necessary.

### MSC:

 94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)

### Keywords:

circuit; Boolean function; fan-in circuits; threshold circuits

Zbl 0753.00019