__
Revision #1 to TR99-001 | 24th August 1999 00:00
__
#### The Complexity of Minimizing and Learning FBDDs Revision of: TR99-001

**Abstract:**
Free Binary Decision Diagrams (FBDDs) or read-once branching

programs are a data structure for Boolean functions. They can

efficiently be manipulated if only FBDDs respecting a fixed graph

ordering are considered. However, the size of such FBDDs may

strongly depend on the chosen graph ordering. In this paper it is

shown that the existence of polynomial time approximation schemes

for optimizing graph orderings or for minimizing FBDDs implies

NP=P, and so such algorithms are quite unlikely to exist. The same

holds for the related problem of computing minimal size FBDDs that

are consistent with a given set of examples. The latter result

implies that size bounded FBDDs are not PAC-learnable unless NP=RP.

__
TR99-001 | 4th January 1999 00:00
__

#### The Complexity of Minimizing FBDDs

**Abstract:**
Free Binary Decision Diagrams (FBDDs) are a data structure

for the representation and manipulation of Boolean functions.

Efficient algorithms for most of the important operations are known if

only FBDDs respecting a fixed graph ordering are considered. However,

the size of such an FBDD may strongly depend on the chosen graph

ordering and efficient algorithms for computing good or optimal graph

orderings are not known. In this paper it is shown that the existence

of polynomial time approximation schemes for optimizing graph

orderings or for minimizing FBDDs implies NP=ZPP or NP=P,

respectively, and so such algorithms are quite unlikely to exist.