Hardness of identifying the minimum ordered binary decision diagram

摘要

An ordered binary decision diagram (OBDD) is a graph representation of a Boolean function. We consider minimum OBDD identification problems: given positive and negative examples of a Boolean function, identify the OBDD with minimum 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 for some fixed f(n) under the PAC-learning model unless NP = RP. We also show 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. [References: 16]