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.

  • $\begingroup$ 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. $\endgroup$
    – holf
    Jan 24 '17 at 13:07
  • $\begingroup$ @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? $\endgroup$
    – 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|)$.

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


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.