On Submodular Complexity Measures
Alexander Alexandrovich Razborov · Cambridge University Press eBooks · 1992
Introduction In recent years several methods have been developed for obtaining superpolynomial lower bounds on the monotone formula and circuit size of explicitly given Boolean functions. Among these are the method of approximations, the combinatorial analysis of a communication problem related to monotone depth and the use of matrices with very particular rank properties. Now it can be said almost surely that each of these methods would need considerable strengthening to yield nontrivial lower bounds for the size of circuits or formulae over a complete basis. So, it seems interesting to try to understand from the formal point of view what kind of machinery we lack. The first step in that direction was undertaken by the author in. In that paper two possible formalizations of the method of approximations were considered. The restrictive version forbids the method to use extra variables. This version was proven to be practically useless for circuits over a complete basis. If extra variables are allowed (the second formalization) then the method becomes universal, i.e. for any Boolean function f there exists an approximating model giving a lower bound for the circuit size of f which is tight up to a polynomial. Then the burden of proving lower bounds for the circuit size shifts to estimating from below the minimal number of covering sets in a particular instance of “MINIMUM COVER” . One application of an analogous model appears in where the first nonlinear lower bound was proven for the complexity of MAJORITY with respect to switching-and-rectifiers networks.