A Class of Boolean Functions with Linear Combinatorial Complexity

Abstract

In this paper we investigate the combinatorial complexity of Boolean functions satisfying a certain property, P^nk,m. A function of n variable has the P^nk,m property if there are at least m functions obtainable from each way of restricting it to a subset of n-l variables. We show that the complexity of P^n3,5 function is no less than 7n-4/6, and this bound cannot be much improved. Further, we find that for each k, there are p^k,2^k functions with complexity linear in n.