What is the minimum size of a circuit that computes PARITY?

Question

It is a classic result that every fan-in 2 AND-OR-NOT circuit that computes PARITY from the input variables has size at least $3(n-1)$ and this is sharp. (We define size as the number of AND and OR gates.) The proof is by gate-elimination and it seems to fail if we allow arbitrary fan-in. What is known for this case?

Specifically, does anyone know an example when larger fan-in helps, i.e., we need less than $3(n-1)$ gates?

Update Oct 18. Marzio has shown that for $n=3$ even $5$ gates suffice using the CNF form of PARITY. This implies a bound of $\lfloor \frac 52 n \rfloor-2$ for general $n$. Can YOU do better?

Answer 1

It is possible to compute parity using only 2.33n + C gates. The construction is quite simple and is given in this article.

http://link.springer.com/article/10.3103/S0027132215050083

Here is an example of a circuit for parity of 6 variables using only 12 gates (each gate is an AND-gate, a circle near the input of a gate means that this input is inverted). Note that a circuit for parity of 6 variables that is constructed by stacking DNF-blocks (like in Marzio’s upper bound) consists of 13 gates.

I have checked that for n=2,3,4,5,6 sizes of optimal circuits are 3,5,8,10,12. These values are also sizes of circuits that give 2.33n upper bound. I still don’t know if 2.33n is the size of optimal circuit for every n. Even more, I don’t know the size of optimal circuit for parity of 7 variables (there are two possible values, 14 and 15).

Answer 2

This gate-elimination lower bound does not match Marzio’s upper bound, but it’s a start.

Proposition: Every unbounded fan-in AND/OR/NOT circuit computing parity on $n\ge2$ variables contains at least $2n-1$ AND and OR gates.

For convenience, I will use a model where the only gates are AND-gates, but we allow negation wires. It is easy to see that $3$ gates are necessary for $n=2$, hence it is enough to show that if $C$ is a minimal-size circuit computing parity on $n>2$ variables, we can find a restriction of one variable which kills at least two gates.

If some variable $x_i$ has at least two positive parents (i.e., it is connected by unnegated wires to two different gates), setting this variable to $0$ will kill the parents and we are done; likewise if it has two negative parents. We may thus assume that each variable has at most one positive and at most one negative parent.

Let $a$ be a bottom-level gate in the circuit. Without loss of generality, $a=x_1\land x_2\land\cdots$. Set $x_1=0$, which forces $a=0$ and kills it. The restricted circuit $C'$ still computes parity, in particular it depends on $x_2$, hence $x_2$ has a negative parent $b=\neg x_2\land c_1\land\dots\land c_r$. Notice that in $C'$, no $c_j$ depends on $x_2$. If there were an assignment to $x_3,\dots,x_n$ which (on top of $x_1=0$) makes some $c_j$ false, the circuit restricted by this assignment would be constant, contradicting the fact that it computes $x_2$ or $\neg x_2$. Thus, in $C'$, all the $c_j$ compute constant $1$, and $b$ computes $\neg x_2$, hence we can eliminate it along with $a$.

EDIT: As I learned from Yuri Kombarov’s paper, this $2n-1$ lower bound, as well as the $\lfloor\frac52n\rfloor-2$ upper bound implied by Marzio De Biasi’s answer, were originally proved in

[1] Ingo Wegener, The complexity of the parity function in unbounded fan-in, unbounded depth circuits, Theoretical Computer Science 85 (1991), no. 1, pp. 155–170. http://dx.doi.org/10.1016/0304-3975(91)90052-4

Answer 3

I expand my comment:

1) a fan-in $k$ AND gate can be simulated by $k-1$ fan-in 2 AND gates (and the same applies to an OR gate); so if $I_i \geq 2$ is the fan-in of gate $g_i$ the following relation must hold:

$$|C| + \sum_i (I_i - 2) \geq 3(n-1)$$

2) if you allow arbitrary fan in then you can beat the $3(n-1)$ bound; for example consider the PARITY on 3 variables $(x_1,x_2,x_3)$; the following circuit computes it with only 5 arbitrary fan-in gates:

Answer 4

This is an extended comment to show what Emil's argument gives if we try proving the $5n/2$ bound. Here we can try to eliminate 3 gates with one variable or 5 gates with two variables.

If there is a literal with 3 parents, we can eliminate all 3 with one variable.

If two literals occur together in 2 different gates, together, we can apply the main argument from Emil's answer, again eliminating 3 gates with one variable.