Computer Science Department
School of Computer Science, Carnegie Mellon University


The Harness of Approximating Minima in OBDDs, FBDDs, and Boolean Functions

Sanjit A. Seshia, Randal E. Bryant

August 2000

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 2i-1. We show that this problem is not approximable to within the factor 2log1-epsilonn, for any epsilon > 0, unless NP is contained in RQP, the class of all problems solvable in random quasi-polynomial 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

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by