期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Ordered binary decision diagrams (OBDDs) and their variants
are motivated by the need to represent Boolean functions
in applications. Research concerning these applications leads
also to problems and results interesting from theoretical
point of view. In this paper, methods from communication
complexity and information theory are combined to prove
that the direct storage access function and the inner product
function have the following property. They have linear
\pi-OBDD size for some variable ordering \pi and, for most
variable orderings \pi', all functions which approximate
them on considerably more than half of the inputs, need
exponential \pi'-OBDD size. These results have implications
for the use of OBDDs in experiments with genetic programming.
关键词：Approximation, genetic programming, Ordered Binary Decision Diagrams, ordering of variables
