Size and Structure of Random Ordered Binary Decision Diagrams

摘要

We investigate the size and structure of ordered binary decision diagrams for rnadom boolean functions. Wegener [Weg94] proved that for "most" values of n, the expected OBDD-size of a random Boolean function with n variables equals the worst-case size up to terms of lower order. Our main result is that this phenomeon, also known as strong shannon effect, shows a threshold behaviour: The strong Shannon effect does not hold wihtin intervals of constant width around the values n=2 sup h+h, but it does hold outside these intervals. Also, the oscillation ofthe expected and the worst-case size is described. Methodical innovations of our apporach are a functional equation to locate"criticla levels" in OBDDs and the use of Azuma's mrtingale inequality and Chvatal's large deviation inequality for the hypergeometric distribution. This leads to significant improvements over wegener' probability bounds.