Exponential lower bounds for restricted monotone circuits

Publisher Website
Google Scholar
Abstract
In this paper we consider monotone Boolean circuits with three alternations, in the order “or”, “and”, “or.” Whenever the number of alternations is limited to a fixed constant the formula and circuit size measures are polynomially related to each other. We shall therefore refer to this measure interchangeably as &Sgr;&pgr;&Sgr;-formula size or &Sgr;&pgr;&Sgr;-circuit size. We shall prove that any such circuit or formula for detecting the existence of cliques in an N-node graph has at least 2&Ohgr;(N&egr;) gates for some &egr; 0 independent of N.

This publication has 0 references indexed in Scilit: