Local complexity of Boolean functions ?
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 ).
complexity boolean functions boolean circuits switching circuits