About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Combinatorica
Paper
The monotone circuit complexity of boolean functions
Abstract
Recently, Razborov obtained superpolynomial lower bounds for monotone circuits that cliques in graphs. In particular, Razborov showed that detecting cliques of size s in a graph m vertices requires monotone circuits of size Ω(m s /(log m)2 s ) for fixed s, and size m Ω(log m) for m/4]. In this paper we modify the arguments of Razborov to obtain exponential lower bounds for circuits. In particular, detecting cliques of size (1/4) (m/log m)2/3 requires monotone circuits exp (Ω((m/log m)1/3)). For fixed s, any monotone circuit that detects cliques of size s requires m) s ) AND gates. We show that even a very rough approximation of the maximum clique of a graph requires superpolynomial size monotone circuits, and give lower bounds for some Boolean functions. Our best lower bound for an NP function of n variables is exp (Ω(n 1/4 · (log n)1/2)), improving a recent result of exp (Ω(n 1/8-ε)) due to Andreev. © 1987 Akadémiai Kiadó.