Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-056 | 22nd April 2008 00:00

On the OBDD complexity of the most significant bit of integer multiplication

RSS-Feed




TR08-056
Authors: Beate Bollig
Publication: 21st May 2008 13:47
Downloads: 3647
Keywords: 


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).



ISSN 1433-8092 | Imprint