 Uniform circuit family

A uniform circuit family $(C_n)$ has one effective rule generating its circuits rather than an independently supplied design at every input length. The precise resource limit on this rule is part of the definition. In logspace uniformity, a Turing machine given $1^n$ outputs a description of $C_n$ using $O(\log n)$ work space; its output tape is not counted as work space.

A family of balanced AND gate trees is uniform: a procedure can enumerate gates and their connections from the input length. In contrast, a nonuniform family can choose the constant output at length $n$ using membership of $n$ in an undecidable set. Those constant circuits are individually tiny, but no algorithm can generate the whole family. Uniformity therefore distinguishes small circuits that can be constructed effectively from arbitrary advice hidden in their choice. Stronger local-access conventions are also used when the circuit depth is so small that the cost of generating a complete description would obscure the intended complexity bound.