文章基本信息

标题：On Random Orderings of Variables for Parity OBDDs
本地全文：下载
作者：Petr Savicky
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：There are Boolean functions such that almost all orderings of its 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 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, then every ordering of the variables yields a parity OBDD for f of size at most s^c.
关键词：OBDD, random ordering of variables, representation of Boolean functions