On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication

Lower-bound results on Boolean-function complexity under two different models are discussed. The first is an abstraction of tradeoffs between chip area and speed in very-large-scale-integrated (VLSI) circuits. The second is the ordered binary decision diagram (OBDD) representation used as a data structure for symbolically representing and manipulating Boolean functions. The lower bounds demonstrate the fundamental limitations of VLSI as an implementation medium, and that of the OBDD as a data structure. It is shown that the same technique used to prove that any VLSI implementation of a single output Boolean function has area-time complexity AT²=Ω(n ²) also proves that any OBDD representation of the function has Ω(cⁿ) vertices for some c>1 but that the converse is not true. An integer multiplier for word size n with outputs numbered 0 (least significant) through 2n-1 (most significant) is described. For the Boolean function representing either output i-1 or output 2n-i-1, where 1⩽i⩽n, the following lower bounds are proved: any VLSI implementation must have AT ²=Ω(i²) and any OBDD representation must have Ω(1.09ⁱ) vertices