Диссертация, Brown University, 1975, -110 pp.
An important open question in the field of computational complexity is the development of nontrivial lower bounds on the number of logical operations required to compute switching functions. Two important measures of functional complexity are combinational complexity, corresponding to the minimal number of operations in any computational chain (straight-line algorithm or feedback-free network) for the function, and formula size. Although counting arguments canpe used to show that most Boolean functions of n inputs and O(n) or fewer outputs have combinational complexity growing approximately exponentially in n, no one has yet exhibited a particular such function whose combinational complexity is known to grow faster than linearly in n when a functionally complete set of primitive operations is allowed. Similarly, it has been demonstrated that most Boolean functions of n variables have a formula size growing approximately exponentially in n, while no specific function is known to have size greater than quadratic in n.
We consider the class of monotone increasing Boolean functions. These correspond to the functions which can be computed using only OR and AND operations, an incomplete set of primitives. We develop techniques for proving functions of n inputs and O(n) outputs have nonlinear combinational complexity if only OR and AND operations are allowed in their computation. We do this by demonstrating the following results:
1) Sorting n binary variables requires O(n log n) OR and O(n log n) AND operations.
2) Certain classes of routing networks require a nonlinear number of operations for their realization. Cyclic and logical shifting of bit strings of length n are shown to have complexity O(n log n).
3) Certain bilinear forms, including the product of an n?n Toeplitz matrix of variables with a column n-vector of variables, the analogous circulant matrix-vector product, and Boolean convolutions, are shown to have combinational complexity lower bounded by O(n log n).
4) It has been proven by others that n3 .ANDs and n3-n2 ORs are necessary and sufficient to compute the Boolean product of two nx n matrices of variables. We extend this result to exhibit a class of bilinear forms computed optimally with the "usual" algorithms.
5) We exhibit a set of n Boolean sums (ORs) over n variables for which O(n3/2) OR operations are both necessary and sufficient.
We also develop nonlinear lower bounds on the formula size of certain monotone increasing Boolean functions,
We also develop a mapping technique to relate the complexity of Boolean functions computed using only OR and AND operations to the complexity of functions computed in other operational bases. This method allows our results to be applied to a far wider class of important problems.
Chapter 1 Introduction
Boolean Functions, Their Computation, and Their Complexity
Properties of Monotone Chains
Chapter 2 Complexity in Other Bases
Asymptotic Bounds
Binary Sorting
Routing Networks
Semidisjoint Bilinear Forms
Disjoint Bilinear Forms
Boolean Sums
Chapter 3 Combinational Complexity
Asymptotic Bounds
Specker's Theorem
Symmetric Functions
Neciporuk's Test
An important open question in the field of computational complexity is the development of nontrivial lower bounds on the number of logical operations required to compute switching functions. Two important measures of functional complexity are combinational complexity, corresponding to the minimal number of operations in any computational chain (straight-line algorithm or feedback-free network) for the function, and formula size. Although counting arguments canpe used to show that most Boolean functions of n inputs and O(n) or fewer outputs have combinational complexity growing approximately exponentially in n, no one has yet exhibited a particular such function whose combinational complexity is known to grow faster than linearly in n when a functionally complete set of primitive operations is allowed. Similarly, it has been demonstrated that most Boolean functions of n variables have a formula size growing approximately exponentially in n, while no specific function is known to have size greater than quadratic in n.
We consider the class of monotone increasing Boolean functions. These correspond to the functions which can be computed using only OR and AND operations, an incomplete set of primitives. We develop techniques for proving functions of n inputs and O(n) outputs have nonlinear combinational complexity if only OR and AND operations are allowed in their computation. We do this by demonstrating the following results:
1) Sorting n binary variables requires O(n log n) OR and O(n log n) AND operations.
2) Certain classes of routing networks require a nonlinear number of operations for their realization. Cyclic and logical shifting of bit strings of length n are shown to have complexity O(n log n).
3) Certain bilinear forms, including the product of an n?n Toeplitz matrix of variables with a column n-vector of variables, the analogous circulant matrix-vector product, and Boolean convolutions, are shown to have combinational complexity lower bounded by O(n log n).
4) It has been proven by others that n3 .ANDs and n3-n2 ORs are necessary and sufficient to compute the Boolean product of two nx n matrices of variables. We extend this result to exhibit a class of bilinear forms computed optimally with the "usual" algorithms.
5) We exhibit a set of n Boolean sums (ORs) over n variables for which O(n3/2) OR operations are both necessary and sufficient.
We also develop nonlinear lower bounds on the formula size of certain monotone increasing Boolean functions,
We also develop a mapping technique to relate the complexity of Boolean functions computed using only OR and AND operations to the complexity of functions computed in other operational bases. This method allows our results to be applied to a far wider class of important problems.
Chapter 1 Introduction
Boolean Functions, Their Computation, and Their Complexity
Properties of Monotone Chains
Chapter 2 Complexity in Other Bases
Asymptotic Bounds
Binary Sorting
Routing Networks
Semidisjoint Bilinear Forms
Disjoint Bilinear Forms
Boolean Sums
Chapter 3 Combinational Complexity
Asymptotic Bounds
Specker's Theorem
Symmetric Functions
Neciporuk's Test