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.

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 there in no
polynomial time approximation scheme for the variable 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\neq NP.