Upper and lower bounds on the OBDD-width of a special integer multiplication
2026-08-31 • Computational Complexity
Computational ComplexityData Structures and Algorithms
AI summaryⓘ
The authors study a specific Boolean function that finds the middle bit of the product when multiplying two numbers given in binary, but only from a limited set of inputs. They focus on how complicated ordered binary decision diagrams (OBDDs) need to be to compute this function, measured by a property called width. They define a new function, s_*(n), related to the problem's structure, and prove that the minimal width of these OBDDs grows exponentially with s_*(n). This work helps understand the computational complexity of representing certain multiplication-related functions.
Boolean functionmiddle bit multiplicationbinary stringsOBDDwidthordered binary decision diagramscomputational complexitycombinatorial functionexponential growth
Authors
Tong Qin
Abstract
We consider the Boolean function ${\rm SMul}_{n-1}^n(\boldsymbol{x},\boldsymbol{y})$, which computes the middle bit of the multiplication of two natural numbers represented as $n$-bit binary strings $\boldsymbol{x}$ and $\boldsymbol{y}$, drawn from a restricted domain. We investigate the width of OBDDs computing ${\rm SMul}_{n-1}^n$. We introduce a combinatorially defined function $s_*(n)$ and show that the width of such OBDDs is $Θ(2^{s_*(n)})$.