ECCC-Report TR99-001https://eccc.weizmann.ac.il/report/1999/001Comments and Revisions published for TR99-001en-usTue, 24 Aug 1999 00:00:00 +0300
Revision 1
| The Complexity of Minimizing and Learning FBDDs Revision of: TR99-001 |
Detlef Sieling
https://eccc.weizmann.ac.il/report/1999/001#revision1Free 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.
Tue, 24 Aug 1999 00:00:00 +0300https://eccc.weizmann.ac.il/report/1999/001#revision1
Paper TR99-001
| The Complexity of Minimizing FBDDs |
Detlef Sieling
https://eccc.weizmann.ac.il/report/1999/001Free 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.
Mon, 18 Jan 1999 16:28:02 +0200https://eccc.weizmann.ac.il/report/1999/001