Circuit size hierarchy #
The argument follows the Boolean cube of truth tables:
BooleanCube.exists_betweengives discrete intermediate values from a bound on coordinate updates.DeMorgan.complexity_dist_lebounds changes in minimum internal gate count by2 * ntimes the ordinary Hamming distance between truth tables.DeMorgan.eventually_exists_complexity_betweencombines interpolation with Shannon counting, reaching every threshold through2^n / n.DeMorgan.polynomialSize_ssubsetprovesSIZE(n^a) ⊊ SIZE(n^b)for all real1 ≤ a < b, including multiplicative constants in the size classes.
These are nonuniform existence results over the native shared circuit model. They do not assert a uniform construction of the separating family.