The complexity of monotone boolean functions

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. © 1978 Springer-Verlag New York Inc.