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?
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 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.
| n \ m | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 (BO) | ||||||||||
| 2 | 1 | 1 | |||||||||
| 3 | 1 | 4 (EF) | 1 | ||||||||
| 4 | 1 | 5 (US) | 5 (EF) | 1 | |||||||
| 5 | 1 | 6 (US) | 8 (JD) | 6 (EF) | 1 | ||||||
| 6 | 1 | 7 (US) | 10 (US) | 10 (JD) | 7 (EF) | 1 | |||||
| 7 | 1 | 8 (US) | 13 (JD) | 17 (JD) | 13 (JD) | 8 (EF) | 1 | ||||
| 8 | 1 | 9 (US) | 15 (JD) | 21 (JD) | 21 (JD) | 15 (JD) | 9 (EF) | 1 | |||
| 9 | 1 | 10 (US) | 19 (JD) | 26 (JD) | 28 (JD) | 26 (JD) | 19 (JD) | 10 (EF) | 1 | ||
| 10 | 1 | 11 (US) | 21 (JD) | 31 (JD) | 34 (JD) | 34 (JD) | 31 (JD) | 21 (JD) | 11 (EF) | 1 | |
| 11 | 1 | 12 (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>2C(n,m)+1, 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.