Complexity lower bound for Boolean functions in the class of extended operator forms

A. S. Baliuk

The Bulletin of Irkutsk State University. Series Mathematics, Tome 30 (2019), pp. 125-140

Résumé

Starting with the fundamental work of D.E.Muller in 1954, the polynomial representations of Boolean functions are widely investigated in connection with the theory of coding and for the synthesis of circuits of digital devices. The operator approach to polynomial representations, proposed in the works of S. F. Vinokurov, made it possible, on the one hand, to uniformly describe all known types of polynomial forms of Boolean functions, and, on the other hand, to generalize them to the case of expansions by the operator images of arbitrary odd function, not only conjunction. In the study of polynomial and, in the general case, operator forms, one of the main questions is obtaining lower and upper bounds of the complexity of the representation of Boolean functions in various classes of forms. The upper bounds of complexity are actually algorithms for minimizing Boolean functions in a particular class of forms. The lower bounds of complexity can be divided into two types: combinatorial and effective. Combinatorial lower bounds make it possible to prove the existence of Boolean functions, having high complexity, without finding the explicit form of these functions. Effective lower bounds are based on explicit constructing Boolean functions that have high complexity in a particular class of forms. In this paper, using an algebraic extension of a finite field of order 2, we obtain a lower bound for the complexity of Boolean functions in the class of extended operator forms. This lower bound strengthens the previously known lower bounds for this class of operator forms and is becoming asymptotically optimal if the sequence of Mersenne primes is infinite.

Détail

Keywords: Boolean function, lower bound, extension of finite field
Mots-clés : Mersenne prime.