THE COMPLEXITY OF THE OPTIMAL VARIABLE ORDERING PROBLEMS OF A SHARED BINARY DECISION DIAGRAM

An ordered binary decision diagram (OBDD) is a directed acyclic graph for representing a Boolean function. OBDDs are widely used in various areas which require Boolean function manipulation, since they can repr esent efficiently many practical Boolean functions and have other desi rable properties. However, there is very little theoretical research o n the complexity of constructing an OBDD. In this paper, we prove that the optimal variable ordering problem of a shared BDD is NP-complete, and briefly discuss the approximation hardness of this problem and re lated OBDD problems.