Premium
On random orderings of variables for parity ordered binary decision diagrams
Author(s) -
Savický Petr
Publication year - 2000
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(200005)16:3<233::aid-rsa1>3.0.co;2-q
Subject(s) - binary decision diagram , boolean function , mathematics , parity (physics) , combinatorics , parity function , random variable , discrete mathematics , binary number , exponential function , algorithm , boolean expression , statistics , arithmetic , mathematical analysis , physics , particle physics
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 ϵ>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 ϵ, where s ≥ n , then every ordering of the variables yields a parity OBDD for f of size at most s c . © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 233–239, 2000