Ordered binary decision diagrams (OBDDs) are a model for representing Boolean functions. There is also a more powerful variant called parity OBDDs. The size of the representation of a given function depends in both these models on the chosen ordering of the variables. It is known that there are functions such that almost all orderings of their variables yield an OBDD of polynomial size, but there are also some exceptional orderings, for which the size is exponential. We prove that for parity OBDDs, the size for a random ordering and the size for the worst ordering are polynomially related. More exactly, for every epsilon > 0 there is a number c > 0 such that the following holds. If a Boolean function f of n variables is such that a random ordering of the variables yields a parity OBDD for f of size at most s with probability at least epsilon, where s greater than or equal to n, then every ordering of the variables yields a parity OBDD for f of size at most s(c). (C) 2000 John Wiley & Sons, Inc. [References: 13]
展开▼
机译：有序二进制决策图（OBDD）是用于表示布尔函数的模型。还有一个更强大的变体，称为奇偶校验OBDD。在这两个模型中，给定函数的表示形式的大小取决于变量的所选顺序。众所周知，存在这样的函数，使得它们的变量的几乎所有排序都产生多项式大小的OBDD，但也有一些例外的排序，其大小是指数的。我们证明，对于奇偶校验OBDD，随机排序的大小和最差排序的大小是多项式相关的。更确切地说，对于每个epsilon> 0，都有一个c> 0的数字，使得以下成立。如果n个变量的布尔函数f使得变量的随机排序产生最大为s的f的奇偶校验OBDD，且概率至少为epsilon，其中s大于或等于n，则变量的每个排序都会产生f大小为s（c）的奇偶校验OBDD。 （C）2000 John Wiley＆Sons，Inc. [参考：13]
展开▼
