Combinational complexity of some monotone functions
- 1 October 1974
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02724847,p. 140-144
- https://doi.org/10.1109/swat.1974.9
Abstract
An important open question in the field of computational complexity in the development of nontrivial lower bounds on the number of logical operations required to compute switching functions. Although counting arguments can be used to show that most Boolean functions of n inputs and 0(n) or fewer outputs have complexity growing exponentially in n, no one has yet exhibited a particular such function whose unlimited fan-out combinational complexity is known to grow faster than linearly in n when a functionally complete set of primitive operations is allowed. In this paper, we consider the class of monotone increasing Boolean functions. These correspond to the functions which can be computed using only two-input OR and AND operations, an incomplete set of primitives. We develop techniques for proving functions of n inputs and 0(n) outputs have nonlinear combinational complexity if only OR and AND operations are allowed. We do this by demonstrating that binary sorting requires 0(n log n) operations, and by exhibiting a set of n Boolean sums over n variables which requires 0(n3/2) operations.Keywords
This publication has 5 references indexed in Scilit:
- The power of negative thinking in multiplying Boolean matricesPublished by Association for Computing Machinery (ACM) ,1974
- Toward a Lower Bound for Sorting NetworksPublished by Springer Nature ,1972
- A Generalization of the Divide-Sort-Merge Strategy for Sorting NetworksPublished by Defense Technical Information Center (DTIC) ,1971
- Complexity in Electronic Switching CircuitsIRE Transactions on Electronic Computers, 1956
- The Synthesis of Two-Terminal Switching CircuitsBell System Technical Journal, 1949