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.