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.
$\begingroup$ $\endgroup$
Add a comment |
2 Answers
$\begingroup$ $\endgroup$
1 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– Leon Leon2011-02-25 15:02:21 +00:00Commented Feb 25, 2011 at 15:02
$\begingroup$ $\endgroup$
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\}$.
