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

Question

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.

Answer 1

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|)$.

[1] Wegener, Ingo. Branching programs and binary decision diagrams: theory and applications. Society for Industrial and Applied Mathematics, 2000.