The Complexity of Monotone Networks for Certain Bilinear Forms, Routing Problems, Sorting, and Merging
Lamagna · IEEE Transactions on Computers · 1979
In this paper, we consider the size of combinational switching networks required to synthesize monotone Boolean functions using only operations from the functionally incomplete set of primitives {disjunction, conjunction}. A general methodology is developed which is used to derive Q(n log n) lower bounds on the size of monotone switching circuits for certain bilinear forms (including Toeplitz and circulant matrix-vector products, and Boolean convolution), certain routing networks (including cyclic and logical shifting), and sorting and merging. A homomorphic mapping technique is also given whereby the lower bounds derived on the sizes of monotone switching networks for Boolean functions can be extended to a larger class of problem domains.