On the complexity of Boolean functions computed by lazy oracles

We introduce and examine some properties of a new complexity measure for Boolean functions. Unlike classical approaches, which are largely concerned with resource requirements, the measure examined here aims at quantifying the potential for lazy evaluation in a function. This measure is motivated by issues arising in the implementation of demand-driven logic simulators. The range of values that can be taken by the measure is precisely identified and a lower bound on the complexity of `almost all´ Boolean functions derived. In addition asymptotically exact values are derived for the class of all Boolean symmetric functions