Title
The Complexity of Monotone Boolean Functions
Document Type
Article
Department
Mathematics (HMC)
Publication Date
1977
Abstract
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.
Rights Information
© 1977 Springer-Verlag
Terms of Use & License Information
DOI
10.1007/BF01768483
Recommended Citation
Pippenger, N. "The Complexity of Monotone Boolean Functions", Math. Sys. Theory, 11 (1978), 289-316. doi: 10.1007/BF01768483
