Problem of the Month (March 2002)

Consider a set of 4 Boolean inputs which are either TRUE or FALSE. The circuit below, built from AND and OR gates, tests whether at least 2 of the inputs are TRUE.

Given integers n and m, let C(n,m) be the smallest number of gates needed to check whether at least m of the n inputs are true. Thus the circuit above shows that C(4,2) ≤ 6. Can you show C(5,3) ≤ 10? Can you do even better than that? What are some other values of C(n,m) ? How does C(n,m) grow for large values of n and m?


ANSWERS

Clearly C(n,1)=1 (all you need is an OR gate) and C(n,n)=1 (all you need is an AND gate). A trivial way to show C(n,n-1) ≤ n+1 is to feed each of the n possible collections of n-1 inputs into an AND gate, and OR the result. These appear to be optimal. For the same reason, C(n,m) ≤ nCm+1, though these appear to be non-optimal for 1 < m < n-1.

Ulrich Schimke and Boris Bukh proved that C(n,m) = C(n,n+1-m). Thus the triangle of values of C(n,m) is symmetric. His proof is a straight-forward use of DeMorgan's laws. If you switch the AND gates and OR gates for the circuit illustrating C(n,m), you get a circuit illustrating C(n,n+1-m) !

Joseph DeVincentis mentioned that this month's puzzle is related to puzzle 12 at Shepherd College. He also found most of the best known circuits.

Brendan Owen noted that you don't need any gates for C(1,1)!

John Hoffman conjectures that maxk C(n,k) grows sub-linearly.

Best Known Upper Bounds on C(n,m)

n \ m1234567891011
10 (BO)
211
314 (EF)1
415 (US)5 (EF)1
516 (US)8 (JD)6 (EF)1
617 (US)10 (US)10 (JD)7 (EF)1
718 (US)13 (JD)17 (JD)13 (JD)8 (EF)1
819 (US)15 (JD)21 (JD)21 (JD)15 (JD)9 (EF)1
9110 (US)19 (JD)26 (JD)28 (JD)26 (JD)19 (JD)10 (EF)1
10111 (US) 21 (JD)31 (JD)34 (JD)34 (JD)31 (JD)21 (JD)11 (EF)1
11112 (US) 27 (JD)36 (JD)42 (JD)42 (JD)42 (JD)36 (JD)27 (JD)12 (EF)1

Here is a circuit for C(5,3) by Joseph DeVincentis and Dane Brooke:

Here is another circuit for C(5,3) by Jorge Mireles:

Boris Bukh considered the problem of binary gates taking only two inputs. He defines D(n,m) to be the fewest number of binary gates to make a "at least m of n" circuit. Clearly D(n,m) ≥ C(n,m). He showed that if 1<m<n, then D(n,m) ≥ 2n-1. This is enough to show that D(4,2)=5.

Boris Bukh also showed that D(n,m) is O(n log n). He conjectures that D(n,m) is o(n log n), since we are essentially computing an order statistic, which is an easier problem than sorting.

Sasha Ravsky notes that this problem can be stated in terms of minimizing the number of conjunctions and disjunctions used to express the disjunction of all the conjunctions containing exactly m different atoms of n atoms. For example, the circuit above for C(5,3) is equivalent to ab(c+d+e)+de(a+b+c)+(a+b)c(d+e). He uses this to prove C(2n,2) ≤ 3n+1, since we can use n conjunctions and 2n+1 disjunctions.

Boris Bukh extended this bound to C(n,m) ≤ 1 + [ m(m+1) log(n) ] / [ log(mm) - log(mm - m!) ] for m>1. His proof is here. He also proved C(n,m) ≥ log2n - 1. His proof: If there are 3 inputs that enter the same set of elements, then the output of the circuit will be the same regardless whether 1 or 2 of these inputs are true, but that would contradict the assumption 2 ≤ m ≤n-1. By Dirichlet's principle, if n>2 * 2C(n,m), then we can find 3 such inputs.

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 1/6/03.