Larger lower bounds on the OBDD complexity of integer multiplication |
| |
Authors: | Beate Bollig |
| |
Affiliation: | LS2 Informatik, TU Dortmund, 44221 Dortmund, Germany |
| |
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: | Communication complexity Computational complexity Integer multiplication Lower bounds Ordered binary decision diagrams |
本文献已被 ScienceDirect 等数据库收录! |
|