The Complexity of Monotone Boolean Functions

Authors

Nicholas Pippenger, Harvey Mudd CollegeFollow

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

Terms of Use for work posted in Scholarship@Claremont.

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