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 x ₁,...,x _n and outputs ¬x ₁,...,¬x _n . We show that (1) For n=2^r–1, circuits computing Parity with r–1 NOT gates have size at least 6n–log₂(n+1)–O(1) and (2) For n=2^r–1, inverters with r NOT gates have size at least 8n–log₂(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 x ₁≥⋯≥x _n . For an arbitraryr, we completely determine the minimum size. For odd n, it is 2n–r–2 for ⌈log₂(n+1)⌉–1≤r ≤n/2, and it is $\lfloor 3/2 \: n\rfloor-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₂(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.