<p>Your question is related to the well-known question about computing the minimum and maximum of a list simultaneously using the minimum number of comparisons. In that case the answer is $3\lfloor n/2 \rfloor$.</p>

<p>The clever algorithm proving the upper bound translates to an AND/OR circuit with same bound you get, since one of the comparisons computes both a minimum and a maximum.</p>

<p>However, the lower bound (given by an adversary argument) does seem to translate, at least in the case of monotone circuits (since an AND/OR circuit translates to a max/min algorithm). This would imply a lower bound of $3\lfloor n/2 \rfloor$. Perhaps a tight lower bound can be obtained by analyzing the adversary argument.</p>

<p>The upper bound appears in "Introduction to Algorithms", where you can also find the easy argument showing that max/min comparator circuits are valid iff they work for boolean inputs (use an appropriate threshold). The lower bound can be found e.g. <a href="http://www.cs.wustl.edu/~sg/CS441_FL01/adv-lb.ps" rel="nofollow">here</a>.</p>

CC BY-SA 3.0
2011-12-03T03:23:18.757Z
Note in Sasha's question, all 2-bit Boolean functions can be used to construct the circuit.
Ryan Williams
CC BY-SA 3.0
2011-12-03T12:18:49.820Z
Yes, it is not clear how the lower bound can be translated to the case of all binary functions.
Alexander S. Kulikov
CC BY-SA 3.0
2011-12-03T01:09:09.663Z
2011-12-03T01:09:09.663Z
Yuval Filmus
<p>This paper of Blum &amp; Seysen may be useful:</p>

<p>N.Blum, M. Seysen. <a href="http://www.springerlink.com/content/m367ku711w732g87/">Characterization of all Optimal Networks for a Simultaneous Computation of AND and NOR</a>. Acta Inf. 21: 171-181 (1984)  </p>

<p>I have thought that for $x_1\dots x_n\vee \bar{x}_1\dots\bar{x}_n$ $2n-c$ lower bound can be obtained using methods of Blum &amp; Seysen, but it seems this is not the case.</p>

CC BY-SA 3.0
2011-12-03T10:31:12.750Z
Is there a public pdf version of the Blum and Seysen paper available?
Marzio De Biasi
CC BY-SA 3.0
2011-12-03T12:20:26.463Z
@Vladimir, thank you for the reference! I will try to check whether their methods are applicable in this case when find the article.
Alexander S. Kulikov
CC BY-SA 3.0
2011-12-03T19:02:12.910Z
@Vladimir, thans again! Actually, this paper contains exactly the answer to my question anv even more: it says that to compute AND and OR simultaneously one needs $2n-2$ and any circuit of this size computes AND and OR _independently_ (this is interesting!). It is also not difficult to show that $C(f_n) \ge C(AND,OR)-c \ge 2n-c'$.
Alexander S. Kulikov
CC BY-SA 3.0
2011-12-03T20:22:49.287Z
@Sasha, yes, I missed this simple construction. To clarify things, in the paper AND and NOR functions are considered, so for AND and OR we get $2n-2$ lower bound by altering one gate and for $x_1\dots x_n\vee \bar{x}_1\dots \bar{x}_n$ --- $2n-5$
Vladimir Lysikov
CC BY-SA 3.0
2011-12-03T20:35:52.807Z
Even better, for $x_1\dots x_n\vee \bar{x}_1\dots \bar{x}_n$ we get the exact complexity $2n-3$ because the construction of $\{AND, NOR\}$ requires 2 additional gates and the resulting circuit is not a "standard network" (pair of independent trees).
Vladimir Lysikov
CC BY-SA 3.0
2011-12-05T08:32:07.323Z
Just a reminder @SashaK. if you like the answer, please "accept" it by clicking on the tick mark below the vote count.
Suresh Venkat
CC BY-SA 3.0
2011-12-14T14:42:47.133Z
@Suresh Venkat, thank you for the remainder! Done.
Alexander S. Kulikov
CC BY-SA 3.0
2011-12-03T01:05:27.473Z
2011-12-04T15:23:09.933Z
2011-12-04T15:23:09.933Z
Vladimir Lysikov
<p>What is the minimal number of binary gates needed to compute AND and OR of $n$ input bits simultaneously?
The trivial upper bound is $2n-2$. I believe that this is optimal, but how to prove this? The standard 
gate elimination technique does not work here as by assigning a constant to any of the input variables
one trivializes one of the outputs. </p>

<p>The problem is also given as an exercise 5.12 in the book "Complexity of Boolean Functions" by Ingo Wegener
in a slightly different form: "Let $f_n(x) = x_1\dots x_n \lor \bar{x}_1 \dots \bar{x}_n$. By the elimination method one
can prove only a lower bound of size $n+\Omega(1)$. Try to prove larger lower bounds."</p>

CC BY-SA 3.0
2011-11-30T17:34:58.430Z
@Ryan: The question is not about AND _of_ OR but about AND _and_ OR.  I do not know the answer to Sasha’s question, though.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-30T18:48:29.427Z
@TsuyoshiIto Thanks, somehow I managed to parse it incorrectly. It is definitely a nontrivial problem -- one could imagine using other kinds of gates to get an advantage over $2n-2$.
Ryan Williams
CC BY-SA 3.0
2011-11-30T21:05:31.967Z
@Sasha, have you tried applying SAT solvers to small examples (like $n=4$), as in some of your earlier papers?
Ryan Williams
CC BY-SA 3.0
2011-12-01T12:24:57.687Z
@Ryan Yes, sure. What we know is that $C_3=3$, $C_4=5$, $C_5 \le 7$. This is for the function from the book (it is $1$ iff all the $n$ input bits are equal). This grows like $2n-3$. And a circuit of size $2n-3$ is easy to construct: first compute $x_i \equiv x_{i+1}$ for all $i=1,\dots,n-1$ ($(n-1)$ gates), and then compute the conjunction of them ($(n-2)$ gates).
Alexander S. Kulikov
CC BY-SA 3.0
2011-12-02T23:58:41.640Z
I fail to understand your method with 2n−3 gates.  What do you mean by “first compute $x_i \equiv x_{i+1}$ for all i=1,…,n−1 (n−1 gates)”?  I do not think that $\equiv$ cannot be implemented with AND and OR gates because $\equiv$ is not monotone.
Tsuyoshi Ito
CC BY-SA 3.0
2011-12-03T00:24:46.760Z
@Tsuyoshi: I think that the $2n-3$ gates function of Sasha is the second function of the question ($f_n(x) = x_1\dots x_n \lor \bar{x}_1 \dots \bar{x}_n$) that can be built with $n-1$ XNOR gates (applied to $x_i,x_{i+1}$) and $n-2$ AND gates applied to the XNORs.
Marzio De Biasi
CC BY-SA 3.0
2011-12-03T00:25:09.413Z
@Vor: I had been incorrectly assuming that the allowed gate set is {AND, OR}, but you are right.  Thanks!
Tsuyoshi Ito
<cc.complexity-theory><lower-bounds><circuit-complexity>
Number of binary gates needed to compute AND and OR of n input bits simultaneously
Alexander S. Kulikov
# Number of binary gates needed to compute AND and OR of n input bits simultaneously

(Asked by: username_0 on 2011-11-30)

What is the minimal number of binary gates needed to compute AND and OR of $n$ input bits simultaneously?
The trivial upper bound is $2n-2$. I believe that this is optimal, but how to prove this? The standard
gate elimination technique does not work here as by assigning a constant to any of the input variables
one trivializes one of the outputs.

The problem is also given as an exercise 5.12 in the book "Complexity of Boolean Functions" by Ingo Wegener
in a slightly different form: "Let $f\_n(x) = x\_1\dots x\_n \lor \bar{x}\_1 \dots \bar{x}\_n$. By the elimination method one
can prove only a lower bound of size $n+\Omega(1)$. Try to prove larger lower bounds."

**Tags:** cc.complexity-theory, lower-bounds, circuit-complexity
> **Comments:**
> **username_1**: @Ryan: The question is not about AND _of_ OR but about AND _and_ OR.  I do not know the answer to Sasha’s question, though.  
> **username_2**: @TsuyoshiIto Thanks, somehow I managed to parse it incorrectly. It is definitely a nontrivial problem -- one could imagine using other kinds of gates to get an advantage over $2n-2$.  
> **username_2**: @Sasha, have you tried applying SAT solvers to small examples (like $n=4$), as in some of your earlier papers?  
> **username_0**: @Ryan Yes, sure. What we know is that $C_3=3$, $C_4=5$, $C_5 \le 7$. This is for the function from the book (it is $1$ iff all the $n$ input bits are equal). This grows like $2n-3$. And a circuit of size $2n-3$ is easy to construct: first compute $x_i \equiv x_{i+1}$ for all $i=1,\dots,n-1$ ($(n-1)$ gates), and then compute the conjunction of them ($(n-2)$ gates).  
> **username_1**: I fail to understand your method with 2n−3 gates.  What do you mean by “first compute $x_i \equiv x_{i+1}$ for all i=1,…,n−1 (n−1 gates)”?  I do not think that $\equiv$ cannot be implemented with AND and OR gates because $\equiv$ is not monotone.  
> **username_3**: @Tsuyoshi: I think that the $2n-3$ gates function of Sasha is the second function of the question ($f_n(x) = x_1\dots x_n \lor \bar{x}_1 \dots \bar{x}_n$) that can be built with $n-1$ XNOR gates (applied to $x_i,x_{i+1}$) and $n-2$ AND gates applied to the XNORs.  
> **username_1**: @Vor: I had been incorrectly assuming that the allowed gate set is {AND, OR}, but you are right.  Thanks!  

---

## 2 answers

### Answer by username_5 on 2011-12-03. Score: 14 | Accepted answer

This paper of Blum & Seysen may be useful:

N.Blum, M. Seysen. [Characterization of all Optimal Networks for a Simultaneous Computation of AND and NOR](http://www.springerlink.com/content/m367ku711w732g87/). Acta Inf. 21: 171-181 (1984)

I have thought that for $x\_1\dots x\_n\vee \bar{x}\_1\dots\bar{x}\_n$ $2n-c$ lower bound can be obtained using methods of Blum & Seysen, but it seems this is not the case.

> **Comments:**
> **username_3**: Is there a public pdf version of the Blum and Seysen paper available?  
> **username_0**: @Vladimir, thank you for the reference! I will try to check whether their methods are applicable in this case when find the article.  
> **username_0**: @Vladimir, thans again! Actually, this paper contains exactly the answer to my question anv even more: it says that to compute AND and OR simultaneously one needs $2n-2$ and any circuit of this size computes AND and OR _independently_ (this is interesting!). It is also not difficult to show that $C(f_n) \ge C(AND,OR)-c \ge 2n-c'$.  
> **username_5**: @Sasha, yes, I missed this simple construction. To clarify things, in the paper AND and NOR functions are considered, so for AND and OR we get $2n-2$ lower bound by altering one gate and for $x_1\dots x_n\vee \bar{x}_1\dots \bar{x}_n$ --- $2n-5$  
> **username_5**: Even better, for $x_1\dots x_n\vee \bar{x}_1\dots \bar{x}_n$ we get the exact complexity $2n-3$ because the construction of $\{AND, NOR\}$ requires 2 additional gates and the resulting circuit is not a "standard network" (pair of independent trees).  
> **username_6**: Just a reminder @SashaK. if you like the answer, please "accept" it by clicking on the tick mark below the vote count.  
> **username_0**: @Suresh Venkat, thank you for the remainder! Done.  

---

### Answer by username_4 on 2011-12-03. Score: 3

Your question is related to the well-known question about computing the minimum and maximum of a list simultaneously using the minimum number of comparisons. In that case the answer is $3\lfloor n/2 \rfloor$.

The clever algorithm proving the upper bound translates to an AND/OR circuit with same bound you get, since one of the comparisons computes both a minimum and a maximum.

However, the lower bound (given by an adversary argument) does seem to translate, at least in the case of monotone circuits (since an AND/OR circuit translates to a max/min algorithm). This would imply a lower bound of $3\lfloor n/2 \rfloor$. Perhaps a tight lower bound can be obtained by analyzing the adversary argument.

The upper bound appears in "Introduction to Algorithms", where you can also find the easy argument showing that max/min comparator circuits are valid iff they work for boolean inputs (use an appropriate threshold). The lower bound can be found e.g. [here](http://www.cs.wustl.edu/~sg/CS441_FL01/adv-lb.ps).

> **Comments:**
> **username_2**: Note in Sasha's question, all 2-bit Boolean functions can be used to construct the circuit.  
> **username_0**: Yes, it is not clear how the lower bound can be translated to the case of all binary functions.  

---

