A theorem of Markov precisely determines the number r(F) of NEGATION gates necessary and sufficient to compute a system of boolean functions F. For a system of boolean functions on n variables, r(F) ≤ [log2(n + 1)]. We call a circuit using the minimum number of NEGATION gates negation-limited. Continuing recent research on negation-limited circuit complexity, we investigate the complexity of negation-limited circuits which compute symmetric functions. First, we shall prove a main technical lemma on functions computed at NEGATION gates in negation-limited circuits computing symmetric functions. Using this lemma, we show a number of lower bounds on the size and depth of negation-limited circuits computing several symmetric functions such as PARITYn, ¬PARITYn, MODkn and others. For example, a 4n + 3 log2 (n + 1) - c lower bound is given on the size of circuits computing the PARITYn function using r(PARITYn) = [log2(n + 1) - 1] NEGATION gates. Furthermore, we show nonlinear lower bounds on the size of certain kinds of negation-limited circuits computing symmetric functions.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Information Systems
- Signal Processing
- Computer Science Applications
- Computational complexity
- Theory of computation