16
$\begingroup$

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."

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Nov 30 '11 at 17:34
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Ryan Williams
    Nov 30 '11 at 18:48
  • 2
    $\begingroup$ @Sasha, have you tried applying SAT solvers to small examples (like $n=4$), as in some of your earlier papers? $\endgroup$
    – Ryan Williams
    Nov 30 '11 at 21:05
  • 2
    $\begingroup$ @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). $\endgroup$
    – Alexander S. Kulikov
    Dec 1 '11 at 12:24
  • 1
    $\begingroup$ @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. $\endgroup$
    – Marzio De Biasi
    Dec 3 '11 at 0:24
14
$\begingroup$

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. 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.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Is there a public pdf version of the Blum and Seysen paper available? $\endgroup$
    – Marzio De Biasi
    Dec 3 '11 at 10:31
  • $\begingroup$ @Vladimir, thank you for the reference! I will try to check whether their methods are applicable in this case when find the article. $\endgroup$
    – Alexander S. Kulikov
    Dec 3 '11 at 12:20
  • 3
    $\begingroup$ @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'$. $\endgroup$
    – Alexander S. Kulikov
    Dec 3 '11 at 19:02
  • $\begingroup$ @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$ $\endgroup$
    – Vladimir Lysikov
    Dec 3 '11 at 20:22
  • 1
    $\begingroup$ Just a reminder @SashaK. if you like the answer, please "accept" it by clicking on the tick mark below the vote count. $\endgroup$
    – Suresh Venkat
    Dec 5 '11 at 8:32
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Note in Sasha's question, all 2-bit Boolean functions can be used to construct the circuit. $\endgroup$
    – Ryan Williams
    Dec 3 '11 at 3:23
  • $\begingroup$ Yes, it is not clear how the lower bound can be translated to the case of all binary functions. $\endgroup$
    – Alexander S. Kulikov
    Dec 3 '11 at 12:18

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.