A Larger Lower Bound on the OBDD Complexity of the Most Significant Bit of Multiplication
From MaRDI portal
Publication:3557025
DOI10.1007/978-3-642-12200-2_24zbMath1283.68132MaRDI QIDQ3557025
Publication date: 27 April 2010
Published in: LATIN 2010: Theoretical Informatics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-12200-2_24
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68P05: Data structures
Related Items
An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order, Randomized OBDDs for the most significant bit of multiplication need exponential space, Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size