Question

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

Short answer

It can be solved using the definitions of parity function, majority function and Branching program.

Step-by-step solution

Definition of Branching Program 

A Branching Program on the variable set $\mathit{x}\mathbf{=}\left\{x_{1.........X_n}\right\}$is a finite directed acyclic graph with one source node & sink nodes partitioned into two sets, Accept & Reject. Each non-sink node is labelled by a variable${\mathit{x}}_{\mathbf{i}}$ & has 2 outgoing edges labelled 0 & 1 respectively.

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

Understanding the definition of Majority function

The function majority $\mathbf{(}\mathit{m}\mathit{a}\mathit{j}\mathit{o}\mathit{r}\mathit{i}\mathit{t}{\mathit{y}}_{\mathbf{n}}\mathbf{:}{\left\{0,1\right\}}^{\mathbf{n}}\mathbf{}\mathbf{Ⓡ}\left\{0,1\right\}\mathbf{)}$, that is defined as:

$$\begin{gathered} \mathit{M}\mathit{A}\mathit{J}\left(x_1,x_2,..x_n\right)\mathbf{=}\mathbf{1}\mathbf{,}\mathit{i}\mathit{f}\mathbf{\sum }_{\mathbf{i}}^{\mathbf{n}}{\mathit{x}}_{\mathbf{i}}\mathbf{}\mathbf{3}\frac{\mathbf{n}}{\mathbf{2}} \\ \mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{=}\mathbf{0}\mathbf{,}\mathit{o}\mathit{t}\mathit{h}\mathit{e}\mathit{r}\mathit{w}\mathit{i}\mathit{s}\mathit{e} \end{gathered}$$

Looking into the Parity function definition

• We Know thatthe parity function with n inputs can be computed by a branching program that has $\mathit{O}\mathbf{\left(}\mathit{n}\mathbf{\right)}$nodes.
• Which can be achieved by building a binary tree of gates that compute XOR function, where XOR function is used as equivalent to the parity function. As we know that two AND’s, two NOT’s and one OR gates are used in the implementation of each XOR gate.
• It is known that AND & OR gates take two nodes as an input and produces a single output which again is considered as an input to the other gate if binary tree is considered.

Hence the total number of nodes, which are used in computation are of an order$\mathit{O}\mathbf{\left(}{\mathbf{2}}^{\mathbf{n}}\mathbf{\right)}$

Therefore, from the definition of Branching Program it can be said thatany function with n inputs can be computed by a branching program that has $\mathit{O}\mathbf{\left(}{\mathbf{2}}^{\mathbf{n}}\mathbf{\right)}$nodes.