Negation-Limited Complexity of Parity and Inverters

Abstract. We give improved lower bounds for the size of negation-limited circuits computing Parity and for the size of negation-limited inverters. An inverter is a circuit with inputs x1,..., xn and outputs ¬x1,..., ¬xn. We show that (1) For n = 2 r −1, circuits computing Parity with r −1 NOT gates have size at least 6n − log 2(n + 1) − O(1) and (2) For n = 2 r − 1, inverters with r NOT gates have size at least 8n − log 2(n + 1) − O(1). We derive our bounds above by considering the minimum size of a circuit with at most r NOT gates that computes Parity for sorted inputs x1 ≥ · · · ≥ xn. For an arbitrary r, we completely determine the minimum size. For odd n, it is 2n − r − 2 for ⌈log 2(n + 1) ⌉ − 1 ≤ r ≤ n/2, and it is ⌊3/2n⌋−1 for r ≥ n/2. We also determine the minimum size of an inverter for sorted inputs with at most r NOT gates. It is 4n−3r for ⌈log 2(n+1) ⌉ ≤ r ≤ n. In particular, the negation-limited inverter for sorted inputs due to Fischer, which is a core component in all the known constructions of negation-limited inverters, is shown to have the minimum possible size. Our fairly simple lower bound proofs use gate elimination arguments.