Back to Search
Start Over
On the OBDD complexity of the most significant bit of integer multiplication
- Source :
-
Theoretical Computer Science . Apr2011, Vol. 412 Issue 18, p1686-1695. 10p. - Publication Year :
- 2011
-
Abstract
- Abstract: 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) . [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 412
- Issue :
- 18
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 59186857
- Full Text :
- https://doi.org/10.1016/j.tcs.2010.12.043