The Shared Gap

A Boolean formula computes by tree: every intermediate result is used exactly once. A Boolean circuit allows sharing: intermediate results can feed multiple gates. The circuit is at most as large as the formula, and the gap between them measures the value of sharing.

Krinkin proves the gap is always exactly 0 or 1.

For any Boolean function, the minimum circuit size is either equal to the minimum formula size or one less. Not two less, not log n less — one. The maximum benefit of sharing, across all possible functions and circuit architectures, is a single gate.

This is unexpected. Circuits can have arbitrary fan-out; a single shared computation can in principle save work that would require exponential duplication in a formula. But at the level of minimum size, the most sharing can ever contribute is removing one redundant gate.

The proof reveals why: optimal formulas already organize computation to minimize redundancy. The tree structure, despite its prohibition on sharing, finds alternative paths that nearly match what sharing achieves. The one remaining gap is structural — a single unavoidable duplication that sharing resolves.

The formula pays almost no price for its restriction. The power of sharing, so dramatic in worst-case examples, reduces to the trivial case at the frontier of optimal computation.