The size of Ordered Binary Decision Diagrams (OBDDs) is determined by the chosen variable ordering. A poor choice may cause an OBDD to be too large to fit into the available memory. The decision variant of the variable ordering problem is known to be NP-complete. We strengthen this result by showing that for each constant c > 1 there is no polynomial time approximation algorithm with the performance ratio c for the variable ordering problem unless P = NP. This result justifies, also from a theoretical point of view, to use heuristics for the variable ordering problem. Instance: An OBDD H for some function f. Problem: Compute a variable ordering minimizing the OBDD size for f and . We remark that from H and each variable ordering an OBDD for f with the variable ordering can be computed in polynomial time (Savický and Wegener (1997) , Meinel and Slobodová (1994) ). Hence, it suffices to define MinOBDD as the problem to compute an optimal variable ordering instead of a minimum size OBDD. MinOBDD is the problem that occurs when applying dynamic variable ordering techniques introduced by Rudell (1993) : When performing computations on OBDDs, e.g. the computation of an OBDD for a function represented by a circuit, the set of functions that are represented changes during this computation. Hence, also the variable orderings admitting small size OBDDs for the represented functions may change. Therefore, it is reasonable to change the variable ordering during the computation. Bryant (1995) reports that this reordering slows down the computation, but that it is sometimes the only possibility to complete computations without exceeding the available memory. The argument for the hardness of the first version of the variable ordering problem does not apply to MinOBDD since the function f is already given as an OBDD, for which the satisfiability test can be done in polynomial time. The first step for proving the hardness of MinOBDD was done by Tani, Hamaguchi and Yajima (1993) . They proved that the decision variant of the problem MinSBDD is NP-complete. SBDDs (shared binary decision diagrams) are the generalization of OBDDs for the representation of more than one function and MinSBDD is the problem to compute an optimal variable ordering for a set of functions given by an SBDD. proved that also the decision variant of MinOBDD is NP-complete. Algorithms for solving the problem MinOBDD exactly are presented in the papers of Ishiura, Sawada and Yajima (1991) and Jeong, Kim and Somenzi (1993) . As expected by the NP-completeness results these algorithms have an exponential worst-case run time. Both algorithms are improvements of the algorithm of Friedman and Supowit (1990) for computing minimum size OBDDs. This algorithm obviously has exponential run time since it works on truth tables. The NP-completeness results justify, also from a theoretical point of view, to apply algorithms that do not necessarily compute optimal solutions. The known heuristics for MinOBDD are based on local search and simulated annealing approaches (see, e.g. Nevertheless, the NP-completeness does not exclude the existence of good approximation algorithms like polynomial time approximation schemes for the variable ordering problem (even if P 6 = NP). The NP-completeness results for MinOBDD and MinSBDD are proved by reductions from the problem Optimal Linear Arrangement. The reductions seem not to be approximation preserving and we do not know of any nonapproximability result for Optimal Linear Arrangement. The only indication that good approximation algorithms for the variable ordering problem do not exist is the unsuccessful search for such algorithms. The known heuristics do not provide any guarantee for the quality of their results. Usually the heuristics are only tested on some set of benchmark circuits. In this paper we characterize the complexity of the variable ordering problem more precisely by proving the following theorem. Theorem 1 If there is some polynomial time approximation algorithm for MinOBDD with the performance ratio c, where c is some constant, then P = NP. 2.
Further, the approximation problem is also hard, as for any constant c > 1 it is NPhard to compute a variable ordering resulting in an OBDD with a size that is at most c times larger than optimal REF ].
The Nonapproximability of OBDD Minimization
Information and Computation
Mathematics Computer Science