This is an idea/question inspired by the question and answer of Boolean functions with exponential size OBDD representation in all orders except one order?:

If you want to prove some exponential lower bounds for some function represented by an ordered binary decision diagram (OBDD) you have to prove this lower bound for every variable ordering (a variable ordering is a permutation on the input variables). Intuitively it is often easy to prove that for a special variable ordering the OBDD size is exponential in the number of input variables. It doesn't need to be one special variable ordering but some variable ordering with some property $P$.

According to my answer to the question mentioned above you can show that there are several variable orderings with polynomial size OBDD if there exists at least one. This contains the statement that you can get several variable orderings from another variable ordering with some blow up in the OBDD size.

I think you can improve this blow up and so the number of variable orderings you can get depending on the function. If you can prove that you can transform every variable ordering to one ordering with property $P$ with a "low" blow up and show that every OBDD with a variable ordering with property $P$ for this function has exponential size you have this lower bound for every variable ordering.

Is this kind of lower bound technique known? Does it seem to be useful if it is not known?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.