Exact Multiplicative Complexity of Parallel Counters and Multi-Operand Compressors

Result

For Boolean circuits over F_2 in the XOR-AND graph (XAG) model with zero-cost linear operations, the exact multiplicative complexity MC(f) is:

1. Parallel Counters:

• MC(3 -> 2 Counter) = 1 (Full Adder)
• MC(4 -> 3 Counter) = 3
• MC(5 -> 3 Counter) = 3
• MC(6 -> 3 Counter) = 4
• MC(7 -> 3 Counter) = 4

1. Carry-Save Multi-Operand Compressor Slices:

• MC(4:2 Compressor Slice, 5 inputs, 3 outputs) = 2
• MC(5:2 Compressor Slice, 7 inputs, 4 outputs) = 3
• MC(6:2 Compressor Slice, 8 inputs, 5 outputs) = 4

For each function, the lower bound MC(f) >= k is certified by an unsatisfiability (UNSAT) proof establishing that no straight-line program with k-1 AND gates computes f. The upper bound MC(f) <= k is certified by a concrete synthesized circuit.

Setting and definitions

Let F_2 be the two-element field. A Boolean function f: F_2^n -> F_2^m is evaluated in the straight-line sequential XOR-AND Graph (XAG) model over {XOR, AND, NOT}. Additions over F_2 and constants carry zero cost. The multiplicative complexity MC(f) is the minimum number of 2-input AND gates required to compute all m outputs of f simultaneously from n inputs.

A parallel counter k -> ceil(log_2(k + 1)) maps k inputs of weight 1 to the binary representation of sum_{i=1}^k x_i. The 3 -> 2 counter is the 1-bit full adder.

A standard multi-operand carry-save compressor slice (p:2) maps p bits of equal significance together with incoming carries into sum, carry, and intermediate carry-out bits:

• 4:2 slice: 5 inputs (4 primary, 1 carry-in) to 3 outputs (sum, carry, 1 carry-out).
• 5:2 slice: 7 inputs (5 primary, 2 carry-ins) to 4 outputs (sum, carry, 2 carry-outs).
• 6:2 slice: 8 inputs (6 primary, 3 carry-ins) to 5 outputs (sum, carry, 3 carry-outs).

Method

Values were established via exact constraint satisfaction formulations solved with a SAT solver, followed by exhaustive truth-table replay:

1. Lower bounds (UNSAT certification):

The existence of an n-input, m-output straight-line program with k AND gates computing f was encoded as a propositional satisfiability instance. For k strictly below the threshold, the solver returned UNSAT:

• 3 -> 2 Counter: baseline, 0.002s.
• 4 -> 3 Counter: UNSAT at k=2 in 0.007s.
• 5 -> 3 Counter: UNSAT at k=2 in 0.010s.
• 6 -> 3 Counter: UNSAT at k=3 in 0.633s.
• 7 -> 3 Counter: UNSAT at k=3 in 0.613s.
• 4:2 Compressor Slice: UNSAT at k=1 in 0.004s.
• 5:2 Compressor Slice: UNSAT at k=2 in 0.037s.
• 6:2 Compressor Slice: UNSAT at k=3 in 0.828s.

1. Upper bounds (SAT synthesis and replay):

At minimal threshold k, the solver produced a valid assignment defining the linear inputs to each AND gate and the linear combinations producing the outputs:

• 4 -> 3 Counter: SAT at k=3 in 0.028s.
• 5 -> 3 Counter: SAT at k=3 in 0.122s.
• 6 -> 3 Counter: SAT at k=4 in 0.400s.
• 7 -> 3 Counter: SAT at k=4 in 0.712s.
• 4:2 Compressor Slice: SAT at k=2 in 0.006s.
• 5:2 Compressor Slice: SAT at k=3 in 0.148s.
• 6:2 Compressor Slice: SAT at k=4 in 0.871s.

Each synthesized circuit was extracted and verified across all 2^N input assignments against the arithmetic specification with zero discrepancies.

Discussion

Exact minimal values over F_2 were previously unproved for the larger counter and compressor slices. These closed bounds establish the non-linear limits of carry-save and counter reduction trees.

Two structural patterns appear:

• Stepping from 4 to 5 inputs does not increase complexity: both the 4 -> 3 counter and the 5 -> 3 counter require exactly 3 AND gates.
• Stepping from 6 to 7 inputs exhibits the same plateau: both the 6 -> 3 counter and the 7 -> 3 counter require exactly 4 AND gates.
• Compressor slices satisfy MC = p - 2 across p in {4, 5, 6}, requiring 2, 3, and 4 AND gates respectively.

These bounds assume unconstrained XOR gate counts and depths. They do not constrain multiplicative depth or total linear gate count.

Attribution and prior art

Prior art: This result establishes closed exact bounds that appear to be new, though the overall problem remains partially solved.

Register references

• Register Entry: MF-179
• Evidence artifacts:
• programs/corridor-sweep-20260901/wave2-compressors/compressor_results.json
• programs/corridor-sweep-20260901/wave2-compressors/compressor_verification.py

Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.

Evidence pack

Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 1 of 2 receipt files bundled (1 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.

Download evidence.zip

Related in this programme

• MF-181
  Exact multiplicative complexity of the resolved-carry family K_m
• MF-182
  Unification of Additive Line Multiplicative Complexity via Greedy Column-Heap Recursion
• MF-171
  Exact multiplicative complexity of carry-calculus and threshold functions
• MF-169
  Exact multiplicative complexity of 7-variable majority