Editing Binary decision diagram (section)

== Logical operations on BDDs ==
Many logical operations on BDDs can be implemented by [[polynomial-time]] graph manipulation algorithms:<ref name="Andersen_1999"/>{{rp|20}}
* [[logical conjunction|conjunction]]
* [[logical disjunction|disjunction]]
* [[negation]]

However, repeating these operations several times, for example forming the conjunction or disjunction of a set of BDDs, may in the worst case result in an exponentially big BDD. This is because any of the preceding operations for two BDDs may result in a BDD with a size proportional to the product of the BDDs' sizes, and consequently for several BDDs the size may be exponential in the number of operations. Variable ordering needs to be considered afresh; what may be a good ordering for (some of) the set of BDDs may not be a good ordering for the result of the operation. Also, since constructing the BDD of a Boolean function solves the NP-complete [[Boolean satisfiability problem]] and the co-NP-complete [[Tautology (logic)|tautology problem]], constructing the BDD can take exponential time in the size of the Boolean formula even when the resulting BDD is small.

Computing existential abstraction over multiple variables of reduced BDDs is NP-complete.<ref name="Huth"/>

Model-counting, counting the number of satisfying assignments of a Boolean formula, can be done in polynomial time for BDDs. For general propositional formulas the problem is [[♯P]]-complete and the best known algorithms require an exponential time in the worst case.