Question

Let${\mathbf{EQ}}_{\mathrm{BP}}\mathbf{=}\mathbf{\{}⟨{\mathbf{B}}_1\mathbf{,}{\mathbf{B}}_{{}_2}⟩$| ${\mathbf{B}}_1$and ${\mathbf{B}}_2$equivalent branching programs.Show that${\mathbf{EQ}}_{\mathrm{BP}}$ is coNP-complete.

Short answer

The above problem can be solved using the method that the branching program is read-once, and have power not more than one. Hence polynomial cannot be more than degree of n . Hence,$\mathit{E}{\mathit{Q}}_{\mathbf{B}\mathbf{P}}$ must be $coNP$.

Step-by-step solution

Considering both B1 and  B2are equivalent branching program

Consider $E{Q}_{BP}=\{B_1,B_2\}|B_1\text{\hspace{0.17em}and\hspace{0.17em}}{B}_2$both are equivalent programme with branches

Acyclic graphs can be used to define branching algorithms $B_1$and $B_2$that can either reject or accept input strings $s_1,s_2,\dots ,s_n$. Turing machines can't solve these problems in their whole, but circuits $coNP$can.

Considering B1 and  B2 is restricted to read-once programs

Consider the problem$E{Q}_{BP}$ that is$B_1$and$B_2$is restricted to read-once programs. By using the equivalence with$coNP$ for testing the equivalence, and by reduction from$co-3SAT$it will be $coNP$.

Polynomial can be determined by following way:

Assign the vertex in programs$E{Q}_{BP}$ for branching, from root to final states.

Label all incoming edges, now vertex polynomials will be sum of polynomials of edge which are incoming.

Polynomial which is associated with final statewill be branching program polynomial.

As the branching program is read-once, and have power not more than one. Hence$E{Q}_{BP}$ polynomial cannot be more than degree of n.

Hence,$E{Q}_{BP}$ must be $coNP$.