Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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".
