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.


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


Zbl 0753.00019