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

Terms of Use for work posted in Scholarship@Claremont.

Link to Full Text

Share

COinS