The Unit Gap: How Sharing Works in Boolean Circuits
This work provides foundational insights into the structure and optimization of Boolean circuits, which is significant for researchers and practitioners in logic synthesis and hardware design.
This paper investigates the difference in size between Boolean circuits (DAGs) and formula circuits (trees) using the AIG basis. It proves that this difference, or 'gap', is always 0 or 1, and that sharing in circuits is only beneficial when the optimal circuit size is greater than or equal to the number of essential variables.
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.