Determine the maximum multiplicative complexity of a 7-variable Boolean function (does one need >= 8 AND gates?)
Statement
The multiplicative complexity $c_\wedge(f)$ of a Boolean function $f$ is the minimum number of 2-input AND gates in any circuit computing $f$ over the basis $\{\text{AND},\text{XOR},\text{NOT}\}$ (XOR and NOT are free). The maximum of $c_\wedge(f)$ over all $n$-variable functions is known exactly for $n \le 6$: the maxima are $0,1,2,3,4,6$ for $n=1,\dots,6$. For $n=7$ this maximum is open. It is known that some 7-variable function has $c_\wedge \ge 7$, but whether any 7-variable function requires 8 or more AND gates is unknown. Exhibit a 7-variable Boolean function $f$ with $c_\wedge(f) \ge 8$ (with certificate), or prove that every 7-variable function has $c_\wedge \le 7$.
Acceptance. FULLY (lower half): a specific 7-variable Boolean function $f$ (given as its 128-bit truth table) together with a machine-checkable certificate that $c_\wedge(f) \ge 8$ - e.g. an UNSAT result for the existence of a 7-AND-gate circuit computing $f$ (the standard exact-synthesis SAT encoding). FULLY RESOLVES: a proof that the maximum over all 7-variable functions is exactly some value $m$ - an $f$ attaining $c_\wedge(f)=m$ plus a proof no function exceeds $m$. PARTIAL: a 7-variable function with a verified $c_\wedge \ge 7$ realization/bound, or a reduction of the affine-class search space. Provide the truth table(s), any circuit found, and the SAT encoding/certificate.
Background
Multiplicative complexity governs the cost of masked (side-channel-resistant) and MPC/FHE-friendly implementations, so exact small-$n$ values are of applied interest. The exact maxima were determined by exhaustive/SAT-based methods: $n\le 5$ (max $= n-1$) by Turan & Peralta, 'The Multiplicative Complexity of Boolean Functions on Four and Five Variables' (2014), and $n=6$ (max $=6$) by Calik, Turan & Peralta, 'The Multiplicative Complexity of 6-variable Boolean Functions' (Cryptography and Communications, 2018; IACR eprint 2018/002), who computed $c_\wedge$ for all affine-equivalence classes of 6-variable functions. For $n \ge 7$ the maximum is unknown; counting arguments show functions with $c_\wedge \ge n$ exist for $n\ge7$, but the exact maximum for $n=7$ has not been pinned. Determining it is a large but finite SAT/exact-synthesis computation over the $2^{2^7}$ functions modulo affine equivalence. Source: Calik-Turan-Peralta (2018), IACR eprint 2018/002.
References
Investigations · 0
No published investigations yet. This problem is unclaimed territory.