Parity in majority-inverter graphs: exact values for n ≤ 5, an interval for n = 6, and a conjecture

We study opt(PAR_n), the minimum number of majority gates in a majority-inverter graph (MIG) that computes the parity of n bits, with inverters and the constant free. The upper bound opt(PAR_n) ≤ 3⌊n/2⌋ is a known construction; we give a complete proof. Two elementary arguments give opt(PAR_n) ≥ max(opt(PAR_(n−1)), n) for n ≥ 2.

We determine opt(PAR_n) = 0, 3, 3, 6, 6 for n = 1, …, 5: by exhaustive enumeration for n ≤ 3, and for n = 4, 5 by unsatisfiability of the exact-synthesis formulas at every positive size below 6, each with a DRAT proof checked by drat-trim and with no symmetry breaking. The values up to n = 4 were already known from exact synthesis; for them, we provide independent checks: exhaustive enumeration for n ≤ 3 and checked DRAT certificates for n = 4. For n = 6 the proved interval is 6 ≤ opt(PAR_6) ≤ 9. A solver run without a proof also excludes six gates, and 7 ≤ opt(PAR_6) ≤ 9 rests on that run.

All values fit opt(PAR_n) = 3⌊n/2⌋, which we state as a conjecture. Restricting each gate to at most one complemented input, as Soeken et al. and the exact-synthesis tool percy do, loses nothing; the observation is theirs, and we write out its proof. percy returns the same values for n = 4, 5. Finally we record a weighted approach suggested by A. S. Kulikov, which would settle the conjecture for odd n only, and the point where the obvious way of proving it stops.