期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：BDD (binary decision diagram) models are motivated
by CAD applications and have led to complexity theoretical
problems and results. Motivated by applications in genetic
programming Krause, Savick\'y, and Wegener (1999) have shown
that for the inner product function IPn and the direct
storage access function DSAn all functions which
approximate them on considerably more than half of the inputs
need exponential -OBDD size for most variable orderings .
In this paper, the results of Krause, Savick\'{y}, and Wegener
are generalized to more general BDD models like k-IBDDs and BP1s
(read-once branching programs). Furthermore, the size of OBDDs for
functions which approximate a function fn is compared with the
size of randomized OBDDs with two sided error for fn. An exponential
gap is presented.
