turkmath.org

The multiplicative complexity of a Booleanfunction is the minimum number of AND gates that are necessary and sufficientto implement the function over the basis (AND, XOR, NOT). Finding the multiplicative complexity of a given function is computationally intractable,even for functions with small number of inputs. Turan et al. showed thatn-variable Boolean functions can be implemented with at most n-1 AND gates forn < 6. A counting argument can be used to show that, for n > 6, thereexist n-variable Boolean functions with multiplicative complexity of at leastn. In this talk, we will describe a method to find the multiplicativecomplexity of Boolean functions by analyzing circuits with a particular numberof AND gates and utilizing the affine equivalence of functions. We use thismethod to study the multiplicative complexity of 6-variable Boolean functions,and calculate the multiplicative complexities of all 150,357 affine equivalence classes. We showthat any 6-variable Boolean function can be implemented using at most 6 ANDgates. Additionally, we exhibit specific 6-variable Boolean functions whichhave multiplicative complexity 6.