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^i-1. We show that this problem is not approximable to within the factor 2^{log1-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 [email protected]