期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
