
CMUCS00156
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS00156
The Harness of Approximating Minima in OBDDs, FBDDs, and Boolean Functions
Sanjit A. Seshia, Randal E. Bryant
August 2000
CMUCS00156.ps
CMUCS00156.pdf
Keywords: Approximation algorithms, complexity theory, approximation
hardness, binary decision diagrams, coding theory, trellises
This paper presents approximation hardness results for three
equivalent problems in Boolean function complexity. Consider
a Boolean function f on n variables. The first problem is to
minimize the level i in the Ordered Binary Decision Diagram
(OBDD) for f at which the number of nodes is less than
2^{i1}.
We show that this problem is not approximable to within the factor
2^{log1epsilonn}, for
any epsilon > 0, unless NP is
contained in RQP, the class of all problems solvable in random
quasipolynomial time. This minimization problem is shown to be
equivalent to the problem of finding the minimum size subset S of
variables so that f has two equivalent cofactors with respect to
the variables in S. Both problems are proved equivalent to the
analogous problem for Free BDDs, and hence the approximation
hardness result holds for all three.
10 pages
