Negation-Limited Complexity of Parity and Inverters

摘要

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_1,…,x_n and outputs -x_1,…, -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_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 x_1≥ … ≥ x_n. 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/2 n」 - 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.