The Unit Gap: How Sharing Works in Boolean Circuits

Abstract

We study the gap between the minimum size of a Boolean circuit (DAG) and the minimum size of a formula (tree circuit) over the And-Inverter Graph (AIG) basis {AND, NOT} with free inversions. We prove that this gap is always 0 or 1 (Unit Gap Theorem), that sharing requires opt(f) >= n essential variables (Threshold Theorem), and that no sharing is needed when opt(f) <= 3 (Tree Theorem). Gate counts in optimal circuits satisfy an exact decomposition formula with a binary sharing term. When the gap equals 1, it arises from exactly one gate with fan-out 2, employing either dual-polarity or same-polarity reuse; we prove that no other sharing structure can produce a unit gap.

Withdrawn: Theorem 2 (the Unit Gap Theorem) is false. For 3-variable parity Khrapchenko forces >= 9 formula leaves (>= 8 gates), yet a 6-gate circuit computes it, so gap >= 2; the true value is 3. The Section 2 recursion uses the DAG measure opt in the children where formula size needs tree. Counterexample and certificates: L. A. Busnello, doi:10.5281/zenodo.21630762. Full notice in v3