Question

Define the function ${\mathrm{majority}}_{\mathrm{n}}:\{0,1{\}}^{\mathrm{n}}\to \{0,1\}$as

$$\begin{gathered} {\mathrm{majority}}_{\mathrm{n}}({\mathrm{x}}_1,\dots ,{\mathrm{x}}_{\mathrm{n}})=\left\{0\sum {\mathrm{x}}_{\mathrm{i}}<\frac{\mathrm{n}}{2}; \\ 1\sum {\mathrm{x}}_{\mathrm{i}}⩾\frac{\mathrm{n}}{2}. \\ \right. \end{gathered}$$

Thus, the${\mathrm{majority}}_{\mathrm{n}}$function returns the majority vote of the inputs. Show that itcan be computed with:

1. $\mathrm{O}({\mathrm{n}}^2)$size circuits.
2. $\mathrm{O}\left(\mathrm{nlogn}\right)$size circuits.

Short answer

1. The first part is solved by implementing the Bubble-sort as a circuit on the n number of inputs taken.
2. The second part is solved by implementing the Merge-sort as a circuit on the n number of inputs taken.

Step-by-step solution

Implementation of Bubble-sort

Now, mimicthe action of the bubble-sort algorithm on an array. It can be implemented one step at a position to be the input n, n-output-sub-circuit that passes through all the inputs taken as

$<k\text{and}⩾k+1$

Now, generate the kth and $k+1st$output using the compare-swap-sub-circuit, which is described on $<kand⩾k+1$which still has the size of two.

Then, implement a pass as the serial concatenation of steps for each of $k=1,2,\dots ,n-1$which has size$\left(n-1\right)*2$

A bubble-sort can proceed to be implemented as the serial concatenation of one pass.

Therefore, this gives a size$1\left(n-1\right)*2=O\left(n^2\right)$

Hence, it can be said that ${\text{majority}}_n$can be computed in $O\left(n^2\right)$size circuits.

Mimicking the Action of the Bubble-sort Algorithm

Let us take n as the number of inputs and implement a merge-sort as a circuit.

It is used to compare two bits after recursively dividing the given inputs in half. The total time taken here $\log n$

Finally, the inputs can be called as $x_1,x_2$and the outputs can be called as $y_1$.

Now, mimic the action of merge-sort algorithm on an array. It can be implemented one step at position to be the input n, n-output-sub-circuit.

Then, implement a pass as the serial concatenation of steps for each of $n \log n$which has size$n*\log n=O\left(n\log n\right)$

Hence, it can be said that ${\text{majority}}_n$can be computed $O\left(n\log n\right)$in size circuits.