Classes of locally complex and locally simple functions are introduced. The classes are proved to be invariant with respect to polynomially equivalent complexity measures. A relationship is considered between proving that a function belongs to a class of locally complex functions and proving lower bounds for Boolean circuits, switching circuits, formulas, and π-circuits (formulas over the basis {&, V,~-}).
展开▼
