Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-052 | 3rd July 2000 00:00

Approximability and Nonapproximability by Binary Decision Diagrams


Authors: Beate Bollig, Ingo Wegener
Publication: 14th July 2000 14:07
Downloads: 1291


Many 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 IP$_n$ and the direct
storage access function DSA$_n$ all functions which
approximate them on considerably more than half of the inputs
need exponential $\pi$-OBDD size for most variable orderings $\pi$.

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 $f_n$ is compared with the
size of randomized OBDDs with two sided error for $f_n$. An exponential
gap is presented.

ISSN 1433-8092 | Imprint