__
TR14-167 | 11th November 2014 12:27
__

#### On the Minimization of (Complete) Ordered Binary Decision Diagrams

**Abstract:**
Ordered binary decision diagrams (OBDDs) are a popular data structure for Boolean functions.

Some applications work with a restricted variant called complete OBDDs

which is strongly related to nonuniform deterministic finite automata.

One of its complexity measures is the width which has been investigated

in several areas in computer science like machine learning, property testing,

and the design and analysis of implicit graph algorithms.

For a given function the size and the width of a (complete) OBDD is very sensitive to

the choice of the variable ordering

but the computation of an optimal variable ordering for the OBDD size is known to be NP-hard.

Since optimal variable orderings with respect to the OBDD size are not

necessarily optimal for the complete model or the OBDD width

and hardly anything about the relation between optimal variable orderings

with respect to the size and the width is known,

this relationship is investigated.

Here, using a new reduction idea it is shown that

the size minimization problem for complete OBDDs and

the width minimization problem are NP-hard.