A class of boolean functions with linear combinational complexity

AbstractIn this paper we investigate the combinational complexity of Boolean functions satisfying a certain property, Pnk,m. A function of n variables has the Pnk,m property if there are at least m functions obtainable from each way of restricting it to a subset of n - - k variables. We show that the complexity of a Pn3,5 function is no less than 7n−46, and this bound cannot be much improved. Further, we find that for each k, there are Pnk,2k functions with complexity linear in n