Limiting negations in bounded-depth circuits: An extension of Markov's theorem
A theorem of Markov shows the necessary and sufficient number of negations for computing an arbitrary collection of Boolean functions. In this paper, we consider a class of bounded-depth circuits, in which each gate computes an arbitrary monotone Boolean function or its negation. We show tight bounds on the number of negations for computing an arbitrary collection of Boolean functions when such a class of circuits is under consideration. (C) 2004 Elsevier B.V. All rights reserved.
computational complexity circuit complexity negation-limited circuits