Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10330773 | Information and Computation | 2011 | 11 Pages |
Abstract
Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations and ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Recently, the question whether the OBDD complexity of the most significant bit of integer multiplication is exponential has been answered affirmatively. In this paper a larger general lower bound is presented using a simpler proof. Furthermore, we prove a larger lower bound for the variable order assumed to be one of the best ones for the most significant bit. Moreover, the best known lower bound on the OBDD complexity for the so-called graph of integer multiplication is improved.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Beate Bollig,