The Complexity of Monotone Boolean Functions
We study the realization of monotone Boolean functions by networks. Our main result is a precise version of the following statement: the complexity of realizing a monotone Boolean function of n arguments is less by the factor (2/πn)1/2, whereπ is the circular ratio, than the complexity of realizing an arbitrary Boolean function of n arguments. The proof combines known results concerning monotone Boolean functions with new methods relating the computing abilities of networks and machines.
© 1977 Springer-Verlag
Pippenger, N. "The Complexity of Monotone Boolean Functions", Math. Sys. Theory, 11 (1978), 289-316. doi: 10.1007/BF01768483