A combinatorial limit to the computing power of V.L.S.I. circuits

Abstract

We introduce a property of boolean functions, called transitivity which holds of integer, polynomial, and matrix products as well as of many interesting related computational problems. We show that the area of any circuit computing a transitive function grows quadratically with the circuit's maximum data-rate, expressed in bit/second. This result provides a precise analytic expression of an area-time tradeoff for a wide class of V.L.S.I. circuits. Furthermore, (as shown elsewhere), this tradeoff is achievable. Thus we have matching (to within a constant multiplicative factor) upper and lower complexity bounds for the three above products, in the V.L.S.I. circuits computational model.