<p>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 &lt; 2i \leq n\}$.</p>

CC BY-SA 3.0
2011-05-24T19:56:40.780Z
2011-05-24T19:56:40.780Z
Stergios Stergiou
<p>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))$.</p>

<p>To see this you can swap neighboring variables in $\pi$, i.e. for $\pi = (x_{\pi(1)}, \ldots, x_{\pi(n)})$ you construct $\pi&#39; = (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&#39;$ 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.</p>

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

CC BY-SA 2.5
2011-02-25T15:02:21.337Z
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: http://cstheory.stackexchange.com/questions/3940/restricted-read-twice-bdds-and-context-free-grammars
Leon Leon
CC BY-SA 2.5
2011-02-25T14:10:40.287Z
2011-02-25T14:10:40.287Z
Marc Bury
<p>Are there boolean functions with exponential size OBDD representation in all orders except one order?</p>

<p>...exponential size in all orders except very few orders?</p>

<p>The exceptional orders should be polysize.</p>

<cc.complexity-theory><boolean-functions><binary-decision-diagrams>
Boolean functions with exponential size OBDD representation in all orders except one order?
Leon Leon
# Boolean functions with exponential size OBDD representation in all orders except one order?

(Asked by: username_0 on 2011-02-25)

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.

**Tags:** cc.complexity-theory, boolean-functions, binary-decision-diagrams

---

## 2 answers

### Answer by username_2 on 2011-02-25. Score: 15 | Accepted answer

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.

> **Comments:**
> **username_0**: 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: http://cstheory.stackexchange.com/questions/3940/restricted-read-twice-bdds-and-context-free-grammars  

---

### Answer by username_1 on 2011-05-24. Score: 3

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\}$.


---

