Editing Binary decision diagram (section)

== Variable ordering ==
The size of the BDD is determined both by the function being represented and by the chosen ordering of the variables. There exist Boolean functions <math>f(x_1,\ldots, x_{n})</math> for which depending upon the ordering of the variables we would end up getting a graph whose number of nodes would be linear (in&nbsp;''n'') at best and exponential at worst (e.g., a [[ripple carry adder]]). Consider the Boolean function <math>f(x_1,\ldots, x_{2n}) = x_1x_2 + x_3x_4 + \cdots + x_{2n-1}x_{2n}.</math> Using the variable ordering <math>x_1 < x_3 < \cdots < x_{2n-1} < x_2 < x_4 < \cdots < x_{2n}</math>, the BDD needs <math>2^{n+1}</math> nodes to represent the function.  Using the ordering <math>x_1 < x_2 < x_3 < x_4 < \cdots < x_{2n-1} < x_{2n}</math>, the BDD consists of <math>2n+2</math> nodes.

{| align="center"
|-
| [[File:BDD Variable Ordering Bad.svg|thumb|638px|BDD for the function ''ƒ''(''x''<sub>1</sub>, ..., ''x''<sub>8</sub>) = ''x''<sub>1</sub>''x''<sub>2</sub> + ''x''<sub>3</sub>''x''<sub>4</sub> + ''x''<sub>5</sub>''x''<sub>6</sub> + ''x''<sub>7</sub>''x''<sub>8</sub> using bad variable ordering]]
| [[File:BDD Variable Ordering Good.svg|thumb|156px|Good variable ordering]]
|}

It is of crucial importance to care about variable ordering when applying this data structure in practice. The problem of finding the best variable ordering is [[NP-hard]].<ref name="Bollig"/> For any constant ''c''&nbsp;>&nbsp;1 it is even NP-hard to compute a variable ordering resulting in an OBDD with a size that is at most ''c'' times larger than an optimal one.<ref name="Sieling"/> However, there exist efficient heuristics to tackle the problem.<ref name="Rice"/>

There are functions for which the graph size is always exponential—independent of variable ordering. This holds e.g. for the multiplication function.<ref name="Bryant1986"/> In fact, the function computing the middle bit of the product of two <math>n</math>-bit numbers does not have an OBDD smaller than <math>2^{\lfloor n/2 \rfloor} / 61 - 4</math> vertices.<ref name="Woelfel_2005"/> (If the multiplication function had polynomial-size OBDDs, it would show that [[integer factorization]] is in [[P/poly]], which is not known to be true.<ref name="Lipton_2009"/>)

Researchers have suggested refinements on the BDD data structure giving way to a number of related graphs, such as BMD ([[binary moment diagram]]s), ZDD ([[zero-suppressed decision diagram]]s), FBDD ([[free binary decision diagram]]s), FDD ([[functional decision diagram]]s), PDD ([[parity decision diagram]]s), and MTBDDs (multiple terminal BDDs).