21
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This paper may be related. The basis, however, here is much larger than AND, OR. $\endgroup$ – Stasys Oct 12 '14 at 9:34
  • $\begingroup$ The following answer is (remotely) related to your question. cstheory.stackexchange.com/questions/3624/… $\endgroup$ – Hermann Gruber Oct 15 '14 at 18:18
  • 1
    $\begingroup$ In both the $3n$ and $\frac52n$ upper bounds, you are actually ignoring negations everywhere rather than just on variables, right? $\endgroup$ – Emil Jeřábek Oct 19 '14 at 16:05
  • 1
    $\begingroup$ How do you do that without duplicating the gate in case it is used both positively and negatively? $\endgroup$ – Emil Jeřábek Oct 19 '14 at 17:52
  • 1
    $\begingroup$ @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! $\endgroup$ – domotorp Oct 21 '14 at 21:39
10
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Yes, so the question is if we can eliminate 5 gates by fixing 2 variables. $\endgroup$ – domotorp Oct 19 '14 at 19:57
  • $\begingroup$ Right. Or even better, if we can eliminate 3 gates by fixing one variable when $n$ is even. $\endgroup$ – Emil Jeřábek Oct 19 '14 at 21:50
8
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nice, indeed for n=3 the CNF has only 5 gates! I wonder if one can do even better in general. $\endgroup$ – domotorp Oct 18 '14 at 21:41
  • $\begingroup$ I didn't think about it too much, but you can surely combine and use in parallel the above circuit and get, for example, a PARITY circuit for 9 variables that uses only 20 gates instead of 24 $\endgroup$ – Marzio De Biasi Oct 18 '14 at 22:36
  • $\begingroup$ I did and I've updated my question. $\endgroup$ – domotorp Oct 19 '14 at 11:55
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.