On the complexity of Boolean functions computed by lazy oracles
Paul E.S. Dunne, Paul H. Leng, Gerald F. Nwana · IEEE Transactions on Computers · 1995
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.>