Question

Show that the majority function with n inputs can be computed by a branching program that has$\mathbf{O}\left(n^2\right)$nodes.

Short answer

To solve the above problem, we need to understand the definition of Branching program i.e., “ a directed acyclic graph where labels of all the nodes are maintained by the variables, except for two output nodes labelled 1 or 0.

Step-by-step solution

Definition of Majority function

In Boolean logic, the majority function is the Boolean function that evaluates to false when half or more argument are false &true otherwise. i.e., the value of the function equals the value of the majority of inputs

The function majority $\left({\text{majority}}_n\text{:}{\left\{0,1\right\}}^n\to \left\{0,1\right\}\right)$, that is defined as:

$$\begin{gathered} MAJ\left(x_1,x_2,\dots z,x_n\right)=1, \text{if} {\sum }_{i=1}^n{x}_i⩾\frac{n}{2} \\ =0, \text{otherwise} \end{gathered}$$

Looking into the definition of Branching Program

A finite directed acyclic graph with one source node & sink nodes partitioned into two sets, Accept & Reject is called as a Branching Program on the variable set $X=\left\{x_1\dots \dots x_n\right\}$. Each non-sink node is labelled by a variable$x_i$ & has 2 outgoing edges labelled 0 & 1 respectively.

An input$x\in {\left\{0,1\right\}}^n$ is accepted if & only if it induces a chain of transitions that lead the start node to a node in Accept.

Solving the problem using the above explanations

Let us take the number of inputs as n. A circuit can be used to implement a bubble sort.

The inputs can be called as $x_1,x_2$and the outputs can be called as $y_1,y_2$. This circuit contains a size of two.

Now, the action of Bubble-sort algorithm can be mimicked on an array.

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

A bubble sort can be Proceeded to implement as the serial concatenation of n passes.

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

Here, AND gates and OR gates are used to construct Branching Program.

Hence, it can be said that the majority function with n inputs can be computed by a branching program that has$O\left(n^2\right)$ nodes.