Related Experiment Video
Updated: Nov 21, 2025

Optimization of Processing of Tiebangchui with Highland Barley Wine Based on the Box-Behnken Design Combined with the Entropy Method
Published on: May 19, 2023
The Multiplicative Complexity of 6-variable Boolean Functions
Çağdaş Çalık1, Meltem Sönmez Turan2, René Peralta1
1National Institute of Standards and Technology.
None:
The multiplicative complexity of a Boolean function is the minimum number of two-input AND gates that are necessary and sufficient to 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. [1] showed that n-variable Boolean functions can be implemented with at most n-1 AND gates for n ≤ 5. A counting argument can be used to show that, for n ≥ 7, there exist n-variable Boolean functions with multiplicative complexity of at least n. In this work, we propose a method to find the multiplicative complexity of Boolean functions by analyzing circuits with a particular number of AND gates and utilizing the affine equivalence of functions. We use this method to study the multiplicative complexity of 6-variable Boolean functions, and calculate the multiplicative complexities of all 150357 affine equivalence classes. We show that any 6-variable Boolean function can be implemented using at most 6 AND gates. Additionally, we exhibit specific 6-variable Boolean functions which have multiplicative complexity 6.
Related Concept Videos
Fundamental Theorem of Algebra
Complex Zeros
Synthetic Disvision of Polynomials
Real Zeros of Polynomials
Combining Functions
Introduction to Polynomial Functions

