Negation-limited circuit complexity of symmetric functions

Keisuke Tanaka, Tetsuro Nishino, Robert Beals

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

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) ≤ [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.

Original languageEnglish (US)
Pages (from-to)273-279
Number of pages7
JournalInformation Processing Letters
Volume59
Issue number5
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'Negation-limited circuit complexity of symmetric functions'. Together they form a unique fingerprint.

Cite this