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 4
n + 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.