Given a general branching program, is there an algorithm which can find an equivalent branching program $P$ of minimal length. That is $|P| \leq |P'|$ for all equivalent branching program $P'$.

If not, are their some specific cases where this algorithm exists?


I'm assuming you mean branching programs in the sense of generalized binary decision diagrams (see here).

Now the question is whether by "length", you mean "size" or "depth". I will answer the "size" version here, as you will most likely mean that (and the depth version has some intricacies).

We can represent a smaller solution in space not larger than the input size. Furthermore, checking two branching programs to be equivalent is a problem contained in the complexity class co-NP.

Hence, we can define an algorithm in $\Sigma^P_2$ (see here) for finding if there exists a smaller equivalent branching program by letting it first guess a smaller solution, and then verify it to be correct using the co-NP equivalence checking oracle.

Note that this may not be an algorithm that is complexity-theoretically optimal. However, the existence of this algorithm answers your question with a "yes".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.