Question

Prove that if Ais a language in L, a family of branching programs$\mathbf{(}{\mathbf{B}}_{\mathbf{1}}\mathbf{,}{\mathbf{B}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{)}$exists wherein each B_naccepts exactly the strings in A of length nand is bounded in size by a polynomial in n.

Short answer

A language with an input length of n is computed in $O\left(nlogn\right)$size circuits by using branching program. Hence, the language A is in logarithmic space.

Step-by-step solution

Define Branching Program

A branching program is defined as a directed acyclic graph where the variables are used to label all the nodes except only two output nodes. The query nodes are defined as all the nodes which are labelled by the variables. All the query nodes consist two outgoing edges, labelled as 0and 1. Both output nodes do not consist of outgoing edges.

Show that the language is in logarithmic space

Consider a language A which takes an input length of n. A set of branching programs is taken in such a way that each branching program accepts exactly the strings in A of length. Now, the Merge-sort IS implemented as a circuit in which the input length of language A has taken as the nodes of the branching program. After recursively dividing the given inputs in to half, it is used to compare two bits. The total time taken here (to divide the inputs into equal halves iteratively) is.

Let the inputs be$x_1,x_2$and the outputs be$y_1,y_2$. Now, the action of the merge-sort algorithm can be mimicked on an array. It is implemented one step at position to be the n-input,$\frac{n}{2}$-output sub-circuit. Now, a pass is implemented as the serial concatenation of steps, which has a size. Therefore, this gives a sizelocalid="1664265778497" $n*logn=O\left(nlogn\right)$.

Hence, it is said that the language A is in logarithmic space. In other words, the language A is in L.