On the OBDD complexity of the most significant bit of integer multiplication
Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations. Ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for boolean functions. Among the many areas of application are verification, model checking, computer-aided design, relational algebra, and symbolic graph algorithms. In this paper it is shown that the OBDD complexity of the most significant bit of integer multiplication is exponential answering an open question posed by Wegener (2000) [18]. (C) 2011 Elsevier B.V. All rights reserved.
integer multiplication ordered binary decision diagrams computational complexity lower bounds