A Simple Constructive Bound on Circuit Size Change Under Truth Table Perturbation
This provides a theoretical foundation for understanding circuit complexity under perturbations, which is incremental but useful for researchers in computational complexity and circuit design.
The paper establishes an explicit bound on how much the optimal circuit size can change when a truth table is perturbed, showing it is at most O(n) for one-point changes and extends to general Hamming distance, with experimental verification at n=4 confirming the bound is tight for AIG circuits.
The observation that optimum circuit size changes by at most $O(n)$ under a one-point truth table perturbation is implicit in prior work on the Minimum Circuit Size Problem. This note states the bound explicitly for arbitrary fixed finite complete bases with unit-cost gates, extends it to general Hamming distance via a telescoping argument, and verifies it exhaustively at $n = 4$ in the AIG basis using SAT-derived exact circuit sizes for 220 of 222 NPN equivalence classes. Among 987 mutation edges, the maximum observed difference is $4 = n$, confirming the bound is tight at $n = 4$ for AIG.