0
$\begingroup$

Are you able to construct a boolean circuit that computes the majority function of n bits where the circuit only takes up O(n) space? If so, what would that circuit look like?

I have a feeling it has to do with a Full Adder, but I am unsure.

$\endgroup$

1 Answer 1

2
$\begingroup$

Interpret each input as a 1-bit number, and sum all the inputs in a binary-tree fashion.

At the $i$-th level of the tree you're dealing with numbers with at most $i+1$ bits. Hence the number of gates on the generic $i$-th level is $O(i \cdot \frac{n}{2^i})$ and the overall number of gates is $O\left( \sum_{i=1}^{\log n} i \frac{n}{2^i} \right) = O(n)$.

Once you have found the sum of the inputs, simply compare it with $\lfloor n/2 \rfloor +1$.

$\endgroup$
6
  • $\begingroup$ I think that makes sense - my last point of confusion would be in that final comparison. How would I perform that final comparison using logical gates? $\endgroup$ Nov 25, 2023 at 23:33
  • $\begingroup$ Also, in the initial circuit - how does adding the individual bits pairwise result in shortening the number of bits to i + 1 - wouldn't each two bits result in a sum and carry bit? I might be misunderstanding what you're saying here $\endgroup$ Nov 25, 2023 at 23:40
  • $\begingroup$ @circuitman324 You can just compare the bits of of the final sum with the bits of $\lfloor n/ 2 \rfloor +1$ one by one, from the most significant digit. As soon as one bit is $1$ while the other is $0$, the number with the $1$ bit is lager. This can be done with a constant number of gates per bit pair (you need to compare the current bit pair while remembering if a decision in which number is larger has already been made). See the Digital Comparator page on wikipedia. $\endgroup$
    – Steven
    Nov 26, 2023 at 9:40
  • $\begingroup$ Assume that $n$ is a power of $2$ (if it's not then the same argument applies with suitable rounding, the asymptotic side of the circuit is not affected). Adding the $n$ individual bits pairwise results in $n/2$ numbers with at most $2$ bits each. Adding these $2$-bit numbers pairwise results in $n/4$ numbers with at most $3$ bits each. In general, on the $i$-th level you add $n/2^{i-1}$ numbers with $i$ bits each and get $n/2^{i}$ numbers with $i+1$ bits each. $\endgroup$
    – Steven
    Nov 26, 2023 at 9:40
  • $\begingroup$ Thanks! I was also wondering - could you elaborate more on how to handle the case where n is not a power of 2? $\endgroup$ Nov 26, 2023 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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