<p>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.</p>

<p><strong>Corollary 5.7.11</strong> (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|)$.</p>

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

CC BY-SA 3.0
2017-01-25T08:14:18.707Z
2017-01-25T08:14:18.707Z
holf
<p>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\}$. </p>

<p>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$. </p>

<p>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?</p>

<p>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.</p>

CC BY-SA 3.0
2017-01-24T13:07:52.550Z
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
CC BY-SA 3.0
2017-01-25T00:18:53.733Z
@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
<circuit-complexity><complexity>
Equivalence for Constant-width Read-Once Branching Programs with Distinct Orders
verifying
# Equivalence for Constant-width Read-Once Branching Programs with Distinct Orders

(Asked by: username_0 on 2017-01-24)

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.

**Tags:** circuit-complexity, complexity
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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?  

---

## 1 answers

### Answer by username_1 on 2017-01-25. Score: 5 | Accepted answer

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.


---

