Are there boolean functions with exponential size OBDD representation in all orders except one order?

...exponential size in all orders except very few orders?

The exceptional orders should be polysize.


If there is an variable ordering $\pi$ such that the OBDD size for $f$ with this ordering is $O(poly(n))$, then a lot of OBDDs with a similar variable ordering has a size of $O(poly(n))$.

To see this you can swap neighboring variables in $\pi$, i.e. for $\pi = (x_{\pi(1)}, \ldots, x_{\pi(n)})$ you construct $\pi' = (x_{\pi(1)}, \ldots, x_{\pi(i)}, x_{\pi(i-1)}, x_{\pi(i+1)}, \ldots, x_{pi(n)})$ for some $i$. The OBDD size for $f$ with variable ordering $\pi'$ is also polynomial because you can store the value of $x_{\pi(i)}$ by doubling the $x_{\pi(i)}$ nodes in the $\pi$-OBDD for $f$. Then you have the information of $x_{\pi(i)}$ and $x_{\pi(i-1)}$ at this nodes and you can use the $\pi$-OBDD to go on.

That means if you swap $O(\log n)$ variables you also have a polynomial size OBDD.

  • $\begingroup$ Thank you! Very clear answer to the dumb question... Off the top of your head can you think of example for advantages of palindrome 2-IBDD: $1..n n..1$ as described here: cstheory.stackexchange.com/questions/3940/… $\endgroup$
    – Leon Leon
    Feb 25 '11 at 15:02

In fact, it can be shown that if an ordering $\pi$ yields an ROBDD of $O(poly(n))$ size then at least $2^{\lfloor {n/2} \rfloor}$ orderings will also lead to ROBDDs of $O(poly(n))$ size, specifically the orderings obtained from $\pi$ after applying any subset of transpositions $\{(x_{\pi(2i-1)}, x_{\pi(2i)}):0 < 2i \leq n\}$.


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.