## Abstract

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) ≤ [log_{2}(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 PARITY_{n}, ¬PARITY_{n}, MOD^{k}_{n} and others. For example, a 4n + 3 log_{2} (n + 1) - c lower bound is given on the size of circuits computing the PARITY_{n} function using r(PARITY_{n}) = [log_{2}(n + 1) - 1] NEGATION gates. Furthermore, we show nonlinear lower bounds on the size of certain kinds of negation-limited circuits computing symmetric functions.

Original language | English (US) |
---|---|

Pages (from-to) | 273-279 |

Number of pages | 7 |

Journal | Information Processing Letters |

Volume | 59 |

Issue number | 5 |

DOIs | |

State | Published - Sep 9 1996 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications

## Keywords

- Computational complexity
- Theory of computation