The complexity of minimizing and learning OBDDs and FBDDs

AbstractOrdered Binary Decision Diagrams (OBDDs) and Free Binary Decision Diagrams (FBDDs) are data structures for Boolean functions. They can efficiently be manipulated if only OBDDs respecting a fixed variable ordering or FBDDs respecting a fixed graph ordering are considered. In this paper, it is shown that the existence of polynomial time approximation schemes for optimizing variable orderings or graph orderings implies NP=P, and so such algorithms are quite unlikely to exist. Similar hardness results are shown for the related problems of computing minimal size OBDDs and FBDDs that are consistent with a given set of examples. The latter result implies that size bounded OBDDs and FBDDs are not PAC-learnable unless NP=RP