On the Existence of Polynomial Time Approximation Schemes for OBDD Minimization

摘要

The size of Ordered Binary Decision Diagrams 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 ofthe variable ordering problem is known to be NP-complete. We strengthen this result by showing that there is no polynomial time apprximation scheme for the varibable ordering problem unless P=NP. We also prove a small lower bound on the performance ratio of a polynomial time approximation algorithm under the assumption P NP.