TCS-TR-A-11-52

Date: Sat Apr 2 22:12:47 2011

Title: Counter Examples to the Conjecture on the Complexity of BDD Binary Operations

Authors: Ryo Yoshinaka, Jun Kawahara, Shuhei Denzumi, Hiroki Arimura and Shin-ichi Minato

Contact:

First name: Shin-ichi
Last name: Minato
Address: Graduate School of Information Science and Technology, Hokkaido University, North 14 West 9, Sapporo, 060-0814, Japa
Email: minato@ist.hokudai.ac.jp

Abstract. In this article, we disprove the long-standing conjecture, proposed by R. E. Bryant in 1986, that any binary operation on two Boolean functions can be performed by his BDD algorithm in input-output linear time. We present Boolean functions for which his algorithm requires quadratic time in the input-output size for any non-trivial binary operation such as $\wedge, \vee$, and $\oplus$. For the operations $\wedge$ and $\vee$, we show a further stronger counterexample such that the output BDD size becomes only a constant but computation time is still quadratic in the input BDD size. We also present experimental results to support our theoretical observations.