Question

Define the functionas in problem9.24. Show that it may be computed with$\mathbf{O}\mathbf{\left(}\mathbf{n}\mathbf{\right)}$size circuits.

Problem 9.24

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

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

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

a. $\mathbf{O}\mathbf{(}{\mathbf{n}}^{\mathbf{2}}\mathbf{)}$ size circuits.

b. localid="1663252609202" $\mathbf{O}\mathbf{\left(}\mathbf{nlogn}\mathbf{\right)}$ size circuits.

Short answer

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

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

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

Consider $x_1,x_2$be the inputs and $y_1,y_2$jn as outputs. A sub-circuit can be written which accomplished this as $y_1=OR\left(x_1,x_2\right)$and $y_2=AND\left(x_1,x_2\right)$. This circuit contains a size of two.

Mimicking the action of Bubble-sort Algorithm

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

$<k$and $⩾k+1$are unchanged.

Now, generate the kth and $k+1st$output using the compare-swap-sub-circuit, which is described on $<k$and $⩾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 implement as the serial concatenation of one pass.

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

This $O\left(n\right)$complexity can be achieved only when the input taken is already in sorted order.

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

Implementing the Merge-sort as a circuit on the n number of inputs taken

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 I to 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, mimicthe 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 in $O\left(n\log n\right)$ size circuits.