Hardness of identifying the minimum ordered binary decision diagram

An ordered binary decision diagram (OBDD) is a graph representation of a Bo olean function. We consider minimum OBDD identification problems: given pos itive and negative examples of a Boolean function, identify the OBDD with m inimum number of nodes (or with minimum width) that is consistent with all the examples. We prove in this paper that the problems are NP-complete. The result implies that f(n)-width OBDD and f(n)-node OBDD are not learnable f or some fixed f(n) under the PAC-learning model unless NP = RP. We also sho w that the problems are still NP-hard even if we restrict the functions to monotone functions. (C) 2000 Elsevier Science B.V. All rights reserved.