TY - JOUR

T1 - Negation-limited circuit complexity of symmetric functions

AU - Tanaka, Keisuke

AU - Nishino, Tetsuro

AU - Beals, Robert

N1 - Funding Information: * Corresponding author. Email: tanaka@jaist.ac.jp. * These results have been previously announced at the 27th ACM STOC, Las Vegas, Nevada, 1995. 2Suppotted by an NSF Mathematical Sciences Postdoctoral Fellowship. 3 Currently visiting DIMACS, Rutgers University, PO. Box 1179, Piscataway, NJ 08855, USA.

PY - 1996/9/9

Y1 - 1996/9/9

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Theory of computation

UR - http://www.scopus.com/inward/record.url?scp=0008454711&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0008454711&partnerID=8YFLogxK

U2 - https://doi.org/10.1016/0020-0190(96)00115-9

DO - https://doi.org/10.1016/0020-0190(96)00115-9

M3 - Article

VL - 59

SP - 273

EP - 279

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 5

ER -