The Realization of Monotone Boolean Functions
Document Type
Conference Proceeding
Department
Mathematics (HMC)
Publication Date
1976
Abstract
In this paper we study the complexity of realizing a monotone but otherwise arbitrary Boolean function. We consider realizations by means of networks and formulae. In both cases the possibility exists that although a monotone function can always be realized in terms of monotone basis functions, a more economical realization may be possible if basis functions that are not themselves monotone are used. Thus, we have four cases, namely: 1. The cost of realizing a monotone function with a network over a universal basis. 2. The cost of realizing a monotone function with a network over a monotone basis. 3. The cost of realizing a monotone function with a formula over a universal basis. 4. The cost of realizing a monotone function with a formula over a monotone basis. For the first case, we obtain a complete solution to the problem. For the other three cases, we obtain improvements over previous results and come within a logarithmic factor or two of a complete solution.
Rights Information
© 1976 ACM
DOI
10.1145/800113.803650
Recommended Citation
Pippenger, Nicholas. "The Realization of Monotone Boolean Functions." ACM Symp. on Theory of Computing, 8 (1976), 204-209.
