A Simple Constructive Bound on Circuit Size Change Under Truth Table Perturbation

Abstract

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.

4 pages, 1 table. Code and data: https://github.com/krinkin/bounds