Abstract:
A set of disjunctions of some variables is constructed and a nonlinear lower bound is proved for the circuit complexity of this set in systems of functional elements (s.f.e.) in a fixed monotone basis. The proposed method for proving the lower bound of circuit complexity in the s.f.e. differs from previously known methods (in a monotone basis).