21

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?

domotorp
  • 13,931
  • 37
  • 93
  • This paper may be related. The basis, however, here is much larger than AND, OR. – Stasys Oct 12 '14 at 09:34
  • The following answer is (remotely) related to your question. http://cstheory.stackexchange.com/questions/3624/practical-consequences-of-parity-notin-ac0?rq=1 – Hermann Gruber Oct 15 '14 at 18:18
  • Not a great intuition: every AND (OR) with fan-in $k$ can be simulated by $k-1$ fan-in 2 ANDs (ORs); so we have $|C| + \sum d_i \geq 3(n-1)$ where $d_i$ is equal to the inputs of gate $g_i$ - 2. – Marzio De Biasi Oct 18 '14 at 00:24
  • 1
    In both the $3n$ and $\frac52n$ upper bounds, you are actually ignoring negations everywhere rather than just on variables, right? – Emil Jeřábek Oct 19 '14 at 16:05
  • @Emil: It makes no difference, as you can always push them to the bottom using De Morgan. – domotorp Oct 19 '14 at 17:36
  • 1
    How do you do that without duplicating the gate in case it is used both positively and negatively? – Emil Jeřábek Oct 19 '14 at 17:52
  • @Emil: Good point! I reedit my question, thx! – domotorp Oct 19 '14 at 19:28
  • Maybe it is trivial, but since it is not mentioned: $PARITY\in \mathrm{NC^1}$ but $PARITY\notin \mathrm{AC^0}$. Sorry if I missed something @mario, but a fan-in $k$ gate can be simulated with $logk$ fan-in 2 gates, not $k-1$. – Harry Oct 21 '14 at 14:45
  • 1
    @Harry: You need k-1 fan-in gates, but they can be placed in depth $\log k$. This question is about SIZE and not DEPTH! – domotorp Oct 21 '14 at 21:39
  • Would you please provide a reference for the 3(n-1) lower bound? – Dandelion Jun 19 '17 at 21:53

4 Answers4

10

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

Emil Jeřábek
  • 17,430
  • 3
  • 61
  • 90
10

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). Circuit for patity of 6 variables

Yuri Kombarov
  • 216
  • 2
  • 6
8

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:

enter image description here

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
2

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.

domotorp
  • 13,931
  • 37
  • 93