Abstract:
We introduce the notion of the depth of branching of a circuit of functional elements and consider classes of circuits of branching depth bounded by a constant. For these classes of circuits over various bases we obtain lower and upper bounds for complexity of a linear Boolean function. We construct infinitely decreasing sequences of measures of complexity for a fixed base and growing branching depth and for a fixed branching depth but varying base.