# Equivalence for Constant-width Read-Once Branching Programs with Distinct Orders

Let $X={x_1,...,x_n}$ be a set of variables and $\pi:[n]\rightarrow [n]$ be a permutation of the $n$-element set $[n]=\{1,...,n\}$.

A $\pi$-OBDD is an oblivious, read-once branching program where the variables are tested in the order $x_{\pi(1)}x_{\pi(2)}...x_{\pi(n)}$. The width of an OBDD $F$ is the maximum number of nodes in a layer of $F$.

Let $c$ be a constant. Given a $\pi_1$-OBDD $F_1$ and a $\pi_2$-OBDD $F_2$, both of width at most $c$, where $\pi_1$ and $\pi_2$ are possibly distinct permutations, what is the complexity of determining whether $F_1$ and $F_2$ represent the same function?

Obs: If $\pi_1 = \pi_2$ then testing whether $F_1$ and $F_2$ represent the same function can be done in polynomial time via classic automata-theoretic techniques.

• What is your reference for the NP-completeness of the problem when $c$ is not constant? Corollary 5.7.11 of "Branching Programs and Binary Decision Diagrams" by Ingo Wegener claims that this can be done in time $O(|F_1||F_2|\log(|F_2|))$. I never read the entire section but the idea is to transform $F_1$ into a minimal $\pi_2$-OBDD. If $F_2$ is equivalent to $F_1$, then we have a bound on this resulting $\pi_2$-OBDD and we can do it in ptime. – holf Jan 24 '17 at 13:07
• @holf you're right. I made a confusion. The NP completeness is with respect to obtaining the best ordering. Could you please post your comment as an answer? – verifying Jan 25 '17 at 0:18

In "Branching Programs and Binary Decision Diagrams" by Ingo Wegener [1] (very good, complete reference to check this kind of fact on branching programs), Section 5.7 deals with how you can transform a given $\pi_1$-OBDD $F_1$ into an equivalent $\pi_2$-OBDD $F_2$ by using syntactic rules. If you have a bound $B$ on the representation of $F_1$ by $\pi_2$-OBDD then you can do this in time polynomial in $|F_1|$ and $B$. He uses it to prove Corollary 5.7.11 which answers your question and a bit more: you do not need to assume the width is bounded.
Corollary 5.7.11 (in [1]): Given $F_1$ a $\pi_1$-OBDD and $F_2$ a $\pi_2$-OBDD, one can check if $F_1$ is equivalent to $F_2$ in time $O(|F_1| \cdot |F_2| \cdot \log |F_2|)$.